本文共 1025 字，大约阅读时间需要 3 分钟。

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

Example:

Input: "25525511135"Output: ["255.255.11.135", "255.255.111.35"]

思路：

合法性的规则：

IP 地址的规律是分4个Part，每个Part是从0-255的数字

0-255的数字，转换成字符，即每个Part 可能由一个字符组成，二个字符组成，或者是三个字符组成。

写一个For循环每一层从1个字符开始取一直到3个字符，再加一个isValid的函数来验证取的字符是否是合法数字，如果是合法的数字，我们再进行下一层递归，否则跳过。

注意：

1. isValid函数边界：有0开头的字符串只有“0”合法

2. 循环判定条件还包括长度

3. 每次判定合法性之后加上substr和“.”

4. 最后只有用完所有字符并且有四个部分才是争取的ip。此时直接验证剩下字符的合法性即可（合法性就保证位数不大于3）

public List
   
     restoreIpAddresses(String s) {        List
    
      res = new ArrayList
     
      ();        if(s.length()==0 || s.equals("") ||s.length()>12)            return res;        dfs(s,0,"",res);        return res;    }        private void dfs(String s,int part, String tmp,List
      
        res){        if(part==3 && isValid(s)){            res.add(tmp+s);            return;        }        for(int i=1;i<4 && i
       
        =0 && value<=255)            return true;        else             return false;    }
       
      
     
    
   

转载地址：http://cnfni.baihongyu.com/