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

链接：

大意：

给定一个只由数字组成的字符串s，要求出其可能的所有的ip地址形式。例子：

思路：

回溯+剪枝。

主要思路就是找ip地址的三个点在s中的位置。

设置一个列表idxs存储三个点的位置，当字符串s的长度大于 3 * (4 - idxs.size()) 或者 小于1 * (4 - idxs.size()) 时，直接退出，表示不满足ip的形式（每一级ip的长度为1，2或3） 

当idxs的大小size达到了3时，表明3个点已经找到了（且对于每个点的左边部分都是满足ip形式的），此时需验证第四部分是否满足ip的规则。如果第四部分的为0开头且不仅一位数字或者第四部分的数字大于255，则直接返回。否则在原来字符串对应位置加上'.'使其成为ip

详情看代码。

代码：

// 找三个点的位置 可以有两个连续的0吗？ 不可以有两个连续的0 0不能开头class Solution {    public List
   
     restoreIpAddresses(String s) {        List
    
      res = new ArrayList<>();        // 提前判断不符合条件的情况        if (s.length() < 4 || s.length() > 12)            return res;        LinkedList
     
       idxs = new LinkedList<>();        dfs(s, idxs, 0, res, s); // index初始为0        return res;    }    // index为上一个点在原字符串（不是子串）的位置    public void dfs (String s, LinkedList
      
        idxs, int index, List
       
         res, String sAll) {        // 长度不满足要求 直接退出        if (s.length() > 3 * (4 - idxs.size()) || s.length() < 1 * (4 - idxs.size()))            return ;        // 找到一种可能的ip        if (idxs.size() == 3) {            // 最后一段不满足ip地址的要求            if (s.charAt(0) == '0' && s.length() > 1 || Integer.parseInt(s) > 255)                 return ;            StringBuilder sb = new StringBuilder();            int i = 0, pos = 0;            //System.out.println(Arrays.toString(idxs.toArray()));            while (i < sAll.length()) {                if (pos < idxs.size() && i == idxs.get(pos)) {                    sb.append(".");                    pos++;                }                sb.append(sAll.charAt(i));                i++;            }            res.add(sb.toString());            return ;        }        int j = 0, num = 0;        while (j < 3 && j < s.length()) {            num = num * 10 + s.charAt(j) - '0';            if(num == 0) { // num == 0时0只能作为ip的某一级，即不能和其他数字组合                idxs.addLast(index + j + 1);                dfs(s.substring(j + 1), idxs, index + j + 1, res, sAll);                idxs.removeLast();                return ;            }            if (num <= 255) {                idxs.addLast(index + j + 1);                dfs(s.substring(j + 1), idxs, index + j + 1, res, sAll);                idxs.removeLast();            }            j++;        }    }}
       
      
     
    
   

结果：

结论：

很有意思的一个回溯题。 

四个月后再刷：

class Solution {    public List
   
     restoreIpAddresses(String s) {        List
    
      res = new ArrayList<>();        if (s.length() < 4 || s.length() > 12)            return res;        for (int p1 = 1; p1 < s.length() - 2; p1++) {            for (int p2 = p1 + 1; p2 < s.length() - 1; p2++) {                for (int p3 = p2 + 1; p3 < s.length(); p3++) {                    dfs(s, res, p1, p2, p3);                }            }        }        return res;    }    // p1,p2,p3: 三个点的位置    public void dfs(String s, List
     
       res, int p1, int p2, int p3) {        String str1 = s.substring(0, p1), str2 = s.substring(p1, p2), str3 = s.substring(p2, p3), str4 = s.substring(p3);        // 四个字符串以0开头 直接返回        if (str1.charAt(0) == '0' && str1.length() > 1 || str2.charAt(0) == '0' && str2.length() > 1 || str3.charAt(0) == '0' && str3.length() > 1 || str4.charAt(0) == '0' && str4.length() > 1) {            return ;        }        int num1 = Integer.parseInt(str1), num2 = Integer.parseInt(str2), num3 = Integer.parseInt(str3), num4 = Integer.parseInt(str4);        // 四个数大于255 直接返回        if (num1 > 255 || num2 > 255 || num3 > 255 || num4 > 255) {            return ;        }        StringBuilder sb = new StringBuilder();        sb.append(s);        sb.insert(p1, '.');        sb.insert(p2 + 1, '.');        sb.insert(p3 + 2, '.');        res.add(sb.toString());        return ;    }}
     
    
   

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