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)

 

思路：要打印所有的结果，只能dfs枚举了。

import java.util.ArrayList;import java.util.List;public class Solution {    public List
      
        restoreIpAddresses(String s) {        List
       
         res = new ArrayList
        
         ();        if (s.length() > 12)            return res;        StringBuilder sb = new StringBuilder();        dfs(res, sb, s, 0);        return res;    }    private void dfs(List
         
           res, StringBuilder sb, String s, int depth) {        // System.out.println("sb:" + sb + ",s:" + s + ",depth:" + depth);        if (depth > 4)            return;        if (depth == 4) {            if (!s.equals(""))                return;            else {                res.add(sb.toString().substring(0, sb.length() - 1));            }        }        for (int i = 1; i <= s.length() && i <= 3; i++) {            String toInsert = s.substring(0, i);            if (isValid(toInsert)) {                sb.append(toInsert + ".");                dfs(res, sb, s.substring(i), depth + 1);                sb.delete(sb.length() - i - 1, sb.length());            }        }    }    private boolean isValid(String toInsert) {        int num = Integer.parseInt(toInsert);        if (num > 255)            return false;        if (num != 0 && toInsert.startsWith("0") || num == 0 && !toInsert.equals("0"))            return false;        return true;    }    public static void main(String[] args) {        String s = "010010";        System.out.println(new Solution().restoreIpAddresses(s));    }}
         
        
       
      

 

第二遍记录：

　　注意用level控制递归的层次。

　　注意StringBuilder删除的方法。

　　注意valid的条件。

public class Solution {    public List
     
       restoreIpAddresses(String s) {        List
      
        res = new ArrayList
       
        ();        if (s.length() > 12 || s.length() < 4)            return res;        StringBuilder sb = new StringBuilder();        restoreIp(res, sb, s, 0);        return res;    }    private void restoreIp(List
        
          res, StringBuilder sb, String s, int level) {        if (level > 4)            return;        if (level == 4) {            if (s.equals("")) {                res.add(sb.toString().substring(0, sb.length() - 1));            } else                return;        }        for (int i = 1; s.length() >= i && i < 4; i++) {            String toInsert = s.substring(0, i);            if (isValid(toInsert)) {                sb.append(toInsert + '.');                restoreIp(res, sb, s.substring(i), level + 1);                sb.delete(sb.length() - i - 1, sb.length());            }        }    }    private boolean isValid(String s) {        int num = Integer.parseInt(s);        if (num > 255)            return false;        if (num != 0 && s.startsWith("0") || num == 0 && !s.equals("0"))            return false;        return true;    }}
        
       
      
     

 

第三遍记录：

　　注意level的运用，>4的情况直接终止。

　　注意每次取substring的时候，注意判断是否超出范围。