1
class Solution {
2
  public List<String> restoreIpAddresses(String s) {
3
    List<String> ans = new ArrayList<>();
4

5
    int len = s.length();
6
    for (int i = 1; i < 4 && i < len - 2; i++) {
7
      for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
8
        for (int k = j + 1; k < j + 4 && k < len; k++) {
9
          String s1 = s.substring(0, i);
10
          String s2 = s.substring(i, j);
11
          String s3 = s.substring(j, k);
12
          String s4 = s.substring(k, len);
13
          if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
14
            ans.add(s1 + "." + s2 + "." + s3 + "." + s4);
15
        }
16
      }
17
    }
18
    return ans;
19
  }
20

21
  boolean isValid(String s) {
22
    if (s.length() > 3
23
        || s.length() == 0
24
        || (s.charAt(0) == '0' && s.length() > 1)
25
        || Integer.parseInt(s) > 255) return false;
26
    return true;
27
  }
28
}