LeetCode 93 Restore IP Addresses

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)

看到題目躺苦，和combination或是subset非常像，都是數(shù)組組合問題祈匙，所以直接想到了backtracing！Ｓ瓢啊！然而問題來了，回溯的時(shí)候到底終止條件是什么赖条？循環(huán)條件又是什么Ｈ缧ⅰＯ芰ā！

真的被自己蠢哭了第晰，寫了兩遍都沒有寫對(duì)锁孟，發(fā)現(xiàn)是自己邏輯錯(cuò)誤。茁瘦。品抽。

終止條件不難，可以在回溯的時(shí)候傳輸一個(gè)segm變量代表當(dāng)前ip含有多少個(gè)segment了甜熔，當(dāng)ip已經(jīng)有4個(gè)segment時(shí)圆恤，即可添加到結(jié)果list中。

那在每次回溯時(shí)腔稀，到底到循環(huán)判斷多少個(gè)元素呢盆昙？！

對(duì)于permutaion和subset和combination來說烧颖，一般都是要循環(huán)遍歷整個(gè)數(shù)組（或字符串）弱左。但對(duì)于combination K，即從n個(gè)數(shù)中選出k個(gè)數(shù)不同的combination的題目炕淮，回溯終止條件變成了index==k拆火。

前面說了句廢話。涂圆。们镜。進(jìn)入正題，那到底需要循環(huán)判斷多少元素呢润歉。

對(duì)于一個(gè)ip模狭，它的segment最多只能有3位（0-255），因此在添加新的segment時(shí)踩衩，只需要考慮當(dāng)前index到index+2這3位數(shù)字即可＝鲤摹７泛骸！

這里還有一個(gè)trick是锚赤，到底數(shù)組（或string）以及ip應(yīng)該怎么傳遞匹舞！
可以考慮每次傳入string的子串（去除當(dāng)前已經(jīng)考慮過的字符）。

代碼：

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> combs = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) return combs;
        dfs(s, combs, "", 0, 0);
        return combs;
    }
    
    public void dfs(String s, List<String> combs, String addr, int segm, int index) {
        if (segm >= 3) {
            String seg = s.substring(index);
            if (isValidSeg(seg)) {
                String ip = addr + seg;
                combs.add(ip);
            }
            return;
        }
        
        for (int i = 1; i < 4 && index+i < s.length(); i++) {
            String seg = s.substring(index, index+i);
            if (isValidSeg(seg)) {
                String ip = addr + seg + ".";
                dfs(s, combs, ip, segm+1, index+i);
            }
        }
            
    }
    
    public boolean isValidSeg(String str) {
        if (str.charAt(0) == '0' && str.length() > 1) return false;
        else if (Integer.valueOf(str) > 255) return false;
        else return true;
    }
    
    public static void main(String[] args) {
        Solution solver = new Solution();
        String s1 = "25525511135";
        String s2 = "0000";
        for (String str : solver.restoreIpAddresses(s1)) {
            System.out.println(str);
        }
        for (String str : solver.restoreIpAddresses(s2)) {
            System.out.println(str);
        }
    }
    
    
}

參考
https://discuss.leetcode.com/topic/3919/my-code-in-java
https://discuss.leetcode.com/topic/53012/a-concise-and-easy-java-solution