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.

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;
    }
}