LeetCodeProblem-Soluation/Restore-IP-Addresses at main · PrinceNagarkoti/LeetCodeProblem-Soluation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private int n;
    private List<String> result;

    public List<String> restoreIpAddresses(String s) {
        result = new ArrayList<>();
        n = s.length();

        if (n > 12) {
            return result;
        }

        solve(s, 0, 0, "");
        return result;
    }

    private boolean isValid(String str) {
        if (str.length() > 1 && str.charAt(0) == '0') {
            return false;
        }
        int val = Integer.parseInt(str);
        return val <= 255;
    }

    private void solve(String s, int idx, int part, String curr) {
        if (idx == n && part == 4) {
            result.add(curr.substring(0, curr.length() - 1));
            return;
        }

        if (idx + 1 <= n) {
            solve(s, idx + 1, part + 1, curr + s.substring(idx, idx + 1) + ".");
        }

        if (idx + 2 <= n && isValid(s.substring(idx, idx + 2))) {
            solve(s, idx + 2, part + 1, curr + s.substring(idx, idx + 2) + ".");
        }

        if (idx + 3 <= n && isValid(s.substring(idx, idx + 3))) {
            solve(s, idx + 3, part + 1, curr + s.substring(idx, idx + 3) + ".");
        }
    }
}