[leetcode] Restore IP Addresses

这条题就是一般的DFS，但要注意corner cases
1. 连续0的时候 要只用第一个 剩下的留给下一代
2. 数字大于255
3. 剪枝，当余下的长度 比 剩下需要用到的数字的max (每段3位最多， 乘与剩下多少段）多的时候 直接return
4. 段数要满足了 再加进去result

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public class Solution { public List<String> restoreIpAddresses(String s) { rec(s, "", 0, 0); return result; } List<String> result = new ArrayList<String>(); public void rec(String s,String fromPrev, int starting, int component){ if (component == 4 || starting >= s.length()) return; if (component == 3){ String leftOver = s.substring(starting); if (leftOver.length() > 3 || Integer.valueOf(leftOver) > 255) return; if (leftOver.charAt(0) == '0' && leftOver.length() > 1) return; result.add(fromPrev+leftOver); return; } for (int i = starting+1; i <= starting+3 && i <= s.length(); i++){ int number = Integer.valueOf(s.substring(starting, i)); if (number < 256){ rec(s, fromPrev+number+".", i, component+1); } if (number == 0) break; } return; } }

public class Solution {
    List result = new ArrayList();
    String s;
    public List restoreIpAddresses(String s) {
        this.s = s;
        findSol("", 0, 0);
        return result;
    }
    
    private void findSol(String currentResult, int currentSection, int currentIndex){
        if ((s.length()-currentIndex) > (4-currentSection)*3){
            return;
        }
        if (currentResult.length() == s.length()+4 && currentIndex == s.length() && currentSection == 4){
            result.add(currentResult.substring(0, currentResult.length()-1));
            return;
        }
        int previousNum=-1;
        for(int i = currentIndex; i < currentIndex+3 && i < s.length();i++){
            Integer a = new Integer(s.substring(currentIndex, i+1));
            if (a.intValue() < 256 && previousNum != 0){
                previousNum = a.intValue();
                findSol(currentResult+a.intValue()+'.', currentSection+1, i+1);
            }
        }
        return;
    }
}