学步园

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 这里的ip地址没有A类，B类，C类讲究；也没有广播地址等讲究。只要判断3个点分开，每个点的数字时从0-255。

2 此类题目能够马上想到应用dfs。

3 每次收录一个新的字符串的字符，与前面的sb组合起来，要进行判断。判断3个方面。是否0-255，是否有超过3个点了，是否01这种现象。

4 如果通过测试，那么还要判断如果是第三个点（终点），那么之后的加入数字不要加点，放入最终结果。如果不是第三个点，还需要加点。

代码

public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> ans = new ArrayList<String>();
        if(s.length()==0||s.length()>12){
            return ans;
        }
        StringBuilder sb = new StringBuilder();
        dfs(s,ans,sb,0);
        return ans;
    }
    
    public boolean isValid(String s ){
        if(s.length()==0||s.length()>3){
            return false;
        }
        int val = Integer.parseInt(s);
        if(!String.valueOf(val).equals(s)){
            return false;
        }
        if(val<0||val>255){
            return false;
        }
        return true;
    }
    
    public void dfs(String s ,ArrayList<String> ans,StringBuilder sb,int level){
        if(level==3){
            if(isValid(s)){
                sb.append(s);
                ans.add(sb.toString());
                sb.delete(sb.length()-s.length(), sb.length());
                return;
            }
        }
        for(int i=0;i<s.length()-1;i++){
            String substr = s.substring(0,i+1);
            if(isValid(substr)){
                sb.append(substr).append(".");
                dfs(s.substring(i+1),ans,sb,level+1);
                sb.delete(sb.length()-1-substr.length(),sb.length());
            }
        }
    }
}