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

For example:

Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

一刷

題解：

1. 題目給定的restoreIpAddresses方法

1. 這里我們首先確定要用到遞歸 + 回溯。 并且我們要了解，合理的ipv4地址是由4段組成，而且每一段的值都在 [0 ， 255] 之間

2. 在這個方法里面，我們要做一些基本的邊界判斷，比如s 是否為null， s的length 是否在 4 和 12之間。

3. 構(gòu)造好用來遞歸求解的方法restoreIp，確定好每個要用的參數(shù)。

4. 返回結(jié)果

2. restoreIp方法

1. 這個方法是我們主要進行處理和判斷的方法。我們也分為兩個部分

2. 判斷并返回結(jié)果:

當我們用來保存ip地址List ip長度已經(jīng)等于4的時候

我們判斷記錄當前position的int pos是否正好等于String s的長度， 假如否，我們返回

否則，這時我們找到一個合理的解?？梢越⒁粋€StringBuilder ipSb，重建出這個ip address，將其加入結(jié)果集 res中，返回

3. 遞歸求解:

這里我們要從i = pos， 到i < s.length() && i < pos + 3來進行遍歷。 因為ip每一部分最多只有3個digit，所以我們有這個pos + 3的constraint

每次先求得當前的ip segment = s.substring(i, pos + 1)

接下來進行判斷， 調(diào)用isIpValid方法

假如當前ip segment合理， 我們將這段ip segment加入到list ip中

遞歸調(diào)用restoreIp(res, list, s, i + 1)進行下一步求解

進行回溯，去除掉之前加入的這段ip segment

否則我們增加i，繼續(xù)嘗試下一個ip segment， 直到i = pos + 3時跳出循環(huán)

3. isIpValid方法

這個方法主要用來確定ip segment是否合理：

首先s為null或者""的時候返回false

當s的首字符為'0'的時候，我們要判斷是否整個s為"0"。 假如是，我們返回true， 假如否，那么這次切割結(jié)果"0x"不合理，我們返回false

求出ip segment的int值，然后返回這個 ipInt是否 >= 0 并且 <= 255

粗略的時間和空間復(fù)雜度估計為O(2n)，但因為有很多的剪枝，有substring()，而且n的范圍是在4和12之間，所以詳細復(fù)雜度并不高，但也并不好算。

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length()<4 || s.length()>12) return res;
        restoreIp(res, new ArrayList<>(), s, 0);
        return res;
    }
    
    private void restoreIp(List<String> res, List<String> ip, String s, int pos){
        if(ip.size() == 4){
            if(pos!=s.length()) return;
            //changeListToString
            String ipString = changeListToString(ip);
            res.add(ipString);
        }
        
        for(int i=pos; i<s.length() && i<pos+3; i++){//maximum is 3 char
            String ipseg = s.substring(pos, i+1);
            if(isValid(ipseg)){
                ip.add(ipseg);
                restoreIp(res, ip, s, i+1);
                ip.remove(ip.size()-1);
            }
        }
    }
    
    private String changeListToString(List<String> ip){
        StringBuilder sb = new StringBuilder();
        for(String str : ip){
            sb.append(str).append(".");
        }
        sb.setLength(sb.length()-1);
        return sb.toString();
    }
    
    private boolean isValid(String s){
        if(s == null || s.length() == 0) return false;
        if(s.charAt(0) == '0') return s.equals("0");
        int num = Integer.parseInt(s);
        return (num>=0 && num<=255);
    }
}

二刷
題解：
對于一個str和起始位置，從起始位置分別截取一段長度為1，2，3的字串，然后進入新的一輪dfs.

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length()<4 || s.length()>12) return res;
        dfs(res, new ArrayList<>(), s, 0);
        return res;
    }
    
    private void dfs(List<String> res, List<String> ip, String s, int pos){
        if(ip.size() == 4){
            if(pos!=s.length()) return;
            //changeListToString
            String ipString = changeListToString(ip);
            res.add(ipString);
        }
        
        for(int i=pos; i<s.length() && i<pos+3; i++){
            String ipseg = s.substring(pos, i+1);
            if(isValid(ipseg)){
                ip.add(ipseg);
                dfs(res, ip, s, i+1);
                ip.remove(ip.size()-1);
            }
        }
    }
    
    private String changeListToString(List<String> ip){
        StringBuilder sb = new StringBuilder();
        sb.append(ip.get(0));
        for(int i=1; i<ip.size(); i++){
            sb.append(".");
            sb.append(ip.get(i));
        }
        return sb.toString();
    }
    
    private boolean isValid(String str){
        if(str == null || str.length() == 0) return false;
        if(str.charAt(0) == '0') return str.equals("0");
        int num = Integer.parseInt(str);
        return (num>=0 && num<=255);
    }
}