Reference: LeetCode EPI 6.9
Difficulty: Medium

My Post: Java Solutions with Explanations and Comments (Backtracking & Iteration)

Problem

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example: 

1
2
3
4
5
6
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Input: "11000"
Output: ["1.10.0.0", "11.0.0.0"]
// Notice that "00" cannot be a valid part

Analysis

Backtracking

The build consists of numbers of each part in an address. It is at most of size $4$. So the base case of the recursive function is when build.size() equals $4$. In terms of whether we should concatenate each part and put it in the result list, we should check if the depth d has reached its end s.length(). If yes, it is a valid address; if no, there are still some elements left and we can’t say it is a valid address.

As for the main part of the recursive function, we should at most consider three characters in the string: d + 0, d + 1, d + 2. But notice that if the first character is 0, then we should not consider the following characters that give 00, 01, 001. All of these combinations are invalid.

To write succinct code, we can first check if the first character is $0$ and then we know whether we should consider $1$ character (0 itself) or $3$ characters as usual (eg. 123). Before backtracking, check if the part we have constructed is valid.

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
public List<String> restoreIpAddresses(String s) {
  int n = s.length();
  List<String> result = new ArrayList<>();
  backtracking(0, s, new ArrayList<>(), result);
  return result;
}

private void backtracking(int d, String s, List<Integer> build, List<String> result) {
  // base case
  if (build.size() == 4) {
    if (d >= s.length()) { // add to the result
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < build.size(); ++i) {
        sb.append(build.get(i));
        if (i < build.size() - 1) sb.append(".");
      }
      result.add(sb.toString());
    }
    return;
  }
  
  // check the first num if it is "0"
  if (d >= s.length()) return;
  int firstNum = s.charAt(d) - '0';
  int count =  (firstNum == 0) ? 1 : 3;
  int sum = 0;
  for (int i = 0; i < count; ++i) {
    if (d + i >= s.length()) break;
    int digit = s.charAt(d + i) - '0';
    sum = sum * 10 + digit;
    if (sum >= 0 && sum <= 255) {
      build.add(sum);
      backtracking(d + i + 1, s, build, result);
      build.remove(build.size() - 1);
    }
  }
}

Time: $O(1)$
Space: $O(1)$

Iteration

We use three loops to express the idea. Before we need a function to determine if a string is a valid part of an address.

1
2
3
4
5
6
private boolean isValidStr(String s) {
  if (s.length() == 0 || s.length() >= 4) return false;
  if (s.startsWith("0") && s.length() >= 2) return false;
  int val = Integer.parseInt(s);
  return val >= 0 && val <= 255;
}

If the length of the string does not satisfy, return false. If the string starts with $0$, we should not consider cases such as 00, 000, etc. We only allow 0 to be in a part. Finally, check the value of the string if it is in [0, 255].

In each loop, we consider strings first, second, third and fourth. The first three strings can be enumerated in three times. For example, first can only be the first three characters in the string.

Note: Remember to check the upper bound index for substring. It should not be greater than n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<String> restoreIpAddresses(String s) {
  int n = s.length();
  List<String> result = new ArrayList<>();
  for (int i = 1; i <= 3 && i <= n; ++i) {
    String first = s.substring(0, i);
    if (isValidStr(first)) {
      for (int j = 1; j <= 3 && i + j <= n; ++j) {
        String second = s.substring(i, i + j);
        if (isValidStr(second)) {
          for (int k = 1; k <= 3 && i + j + k <= n; ++k) {
            String third = s.substring(i + j, i + j + k);
            String fourth = s.substring(i + j + k, n);
            if (isValidStr(third) && isValidStr(fourth)) {
              result.add(first + "." + second + "." + third + "." +  fourth);
            }
          }
        }
      }
    }
  }
  return result;
}

Time: $O(1)$
Space: $O(1)$