# 0093. Restore IP Addresses
###### tags: `Leetcode` `Medium` `FaceBook` `Backtracking`
Link: https://leetcode.com/problems/restore-ip-addresses/
## 思路 O(N) O(N)
原本的想法是用backtracking做，但是有点复杂，有很多情况需要考虑
后来看了别人的解法才发现了这个思路
因为一共有4个数可以填，每个数的长度是1~3，这种有限情况的枚举可以直接用回圈解决，其实和backtracking的核心是一样的
最后检查有没有leading zero是把每个substring转换成数字，再拼接在一起，如果有leading zero在转换成数字的时候就会消失，因此把拼接的string和原来的string长度比较就可以判断有没有leading zero

Time Complexity is O(3^4N) because we are running 4 nested loops of size 3, therefore 3^4 and inside the nested loop we are concatenating the string which takes O(N). Therefore total time complexity is O(3^4N)=O(81*N)~O(N).
Space complexity is O(N) because we are using string ans to concatenate A, B, C, and D.

## Code

class Solution {
    List<String> ans;
    public List<String> restoreIpAddresses(String s) {
        ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int a = 1;a <= 3;a++){
            for(int b = 1;b <= 3;b++){
                for(int c = 1;c <= 3;c++){
                    int d = s.length()-a-b-c;
                    if(d>3 || d<1) continue;
                    int n1 = Integer.parseInt(s.substring(0, a));
                    int n2 = Integer.parseInt(s.substring(a, a+b));
                    int n3 = Integer.parseInt(s.substring(a+b, a+b+c));
                    int n4 = Integer.parseInt(s.substring(a+b+c));
                    // System.out.println(n1+" "+n2+" "+n3+" "+n4);
                    if(n1<=255 && n2<=255 && n3<=255 && n4<=255){
                        sb.append(n1+"."+n2+"."+n3+"."+n4);
                    }
                    if(sb.length() == s.length()+3){
                        ans.add(sb.toString());
                    }
                    sb.setLength(0);
                }
            }
        }
        
        return ans;
    }
}