> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-15-2022-93.md).

# 02/15/2022 93

Method:

Iteratively generate all possible numbers beginning start index. The end index increments from start till the end of the string.

For each of the substring generated, check if it is a valid number.

if the number is valid, concatenate it with "." and increment the dot number and call backtrack with (S, i + 2) as we add dot inside s. 

The base condition is when the dot number is == 3 and we need to check if the fourth part of the number is valid or not. 

Time complexity : O(1) there is not more than `27` combinations to check.

Space complexity : O(1) constant space to keep the solutions, not more than `19` valid IP addresses.

The maximum length of the string is 12 characters. To form an IP address, you need to put a total of three "." between the 12 chracters. There are 11 spaces/slots between the 12 characters.

For the first dot, you are performing 11 Choose 1 which equates to 11. You are considering all 11 slots to put your first dot.

After you placed the first dot, you are left with 10 slots. So for second dot, you are performing 10 Choose 1 which equates to 10.

Finally, you perform 9 choose 1 to find the slot to place your last dot among the remaining 9 slots. 9 choose 1 equates to 9.

Since you are placing each of these three dots successively, the number of possibilities is 11 \* 10 \* 9 = 990. Hope this explains why brute force would consider 990 possibilites in worst case.

class Solution { List result = new ArrayList<>();

```
public List<String> restoreIpAddresses(String s) {
    if(s.length() > 12) return result;
    backtracking(s, 0, 0);
    return result;     
}

private void backtracking(String s, int startIndex, int pointNum){
    if(pointNum == 3){
        if(isValid(s, startIndex, s.length() - 1)){
            result.add(s);
        }
        return;
    }
    
    for(int i = startIndex; i < s.length(); i++){
        if(isValid(s,startIndex, i)){
            s = s.substring(0, i + 1) + "." + s.substring(i + 1);
            pointNum++;
            backtracking(s, i + 2, pointNum); //as we insert an dot inside the s. 
            pointNum--;
            s = s.substring(0, i + 1) + s.substring(i + 2);
        }else{
            break;
        }
        
    }
}

private boolean isValid(String s, int start, int end){
    //if start > end or the length of s is > 3
    if(start > end || end - start > 2) return false;
    //The start can be 0 if the number is 0.
    if(s.charAt(start) == '0' && end > start) return false;
    //The number is between 0 and 255
    if(Integer.valueOf(s.substring(start, end + 1)) > 255) return false;
    return true;
  
}
```

}

public class Solution { public List restoreIpAddresses(String s) { List res = new ArrayList(); int len = s.length(); for(int i = 1; i<4 && i\<len-2; i++){ for(int j = i+1; j\<i+4 && j\<len-1; j++){ for(int k = j+1; k\<j+4 && k\<len; k++){ String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len); if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){ res.add(s1+"."+s2+"."+s3+"."+s4); } } } } return res; } public boolean isValid(String s){ if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255) return false; return true; } }