# Valid Ip Addresses

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

A valid IP address must be in the form of A.B.C.D, where A,B,C and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.

Example:

Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Make sure the returned strings are sorted in order)

Method:

Add three dots to the string, and check if each string is valid.

Solution:

Time: O(n^3)
Space: O(n^3)

public class Solution {
public ArrayList<String> restoreIpAddresses(String A) {
ArrayList<String> result = new ArrayList();
for (int i = 1; i < A.length() - 2; i ++) {
for (int j = i + 1; j < A.length() - 1; j ++) {
for (int k = j + 1; k < A.length(); k ++) {
StringBuilder sb = new StringBuilder(A);
sb.insert(i, '.');
sb.insert(j + 1, '.');
sb.insert(k + 2, '.');
if (isValid(sb.toString())) {
result.add(sb.toString());
}
}
}
}
return result;
}

private boolean isValid(String A) {
String[] arr = A.split("\\.");
for (String a : arr) {
if (a.length() == 0) {
return false;
}
if (a.length() <= 3 && Integer.valueOf(a) <= 255) {
if (a.charAt(0) == '0' && a.length() != 1) {
return false;
}
} else {
return false;
}
}
return true;
}
}