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

DESC:

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

 

示例 1：

输入：s = "25525511135"

输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"

输出：["0.0.0.0"]

示例 3：

输入：s = "1111"

输出：["1.1.1.1"]

示例 4：

输入：s = "010010"

输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"

输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/restore-ip-addresses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

CODE1:

JAVA:

class Solution {    private ArrayList
    
      res = new ArrayList<>();    public List
     
       restoreIpAddresses(String s) {       // write code here        if (s == null || s.length() < 4 || s.length()>12) {            return res;        }        backTrack(s, 0, 3);        return res;    }    private void backTrack(String s, int start, int cnt){        if (cnt == 0) {            String[] ips = s.split("\\.");            if (ips.length < 4) {                return;            }            for (String c: ips) {                if ((c.length()> 1 && c.startsWith("0")) || Integer.parseInt(c) > 255) {                    return;                }            }            res.add(s);            return;        }                if (start >= s.length()) {            return;        }        int len = s.length();        backTrack(s.substring(0,start+1)+"."+s.substring(start+1,len), start+2,cnt-1);        if (start + 2 < len) {            backTrack(s.substring(0,start+2)+"."+s.substring(start+2,len), start+3,cnt-1);        }        if (start + 3 < len) {            backTrack(s.substring(0,start+3)+"."+s.substring(start+3,len), start+4,cnt-1);        }    }}
     
    

 

CODE2:

JAVA:

class Solution {    public int COUNT = 4;    public List
    
      restoreIpAddresses(String s) {       // write code here        if (s == null || s.length() < 4 || s.length()>12) {            return new ArrayList<>(0);        }        List
     
       res = new ArrayList<>();        int[] ipArr = new int[COUNT];        backTrack(res, ipArr, s, 0, 0);        return res;    }    private void backTrack(List
      
        res, int[] ipArr, String s, int id, int startIndex){        if (id == COUNT) {            if (startIndex != s.length()) {                return;            }            StringBuilder sb = new StringBuilder();            for (int i=0; i
       
        01这种不符合条件        if (s.charAt(startIndex) == '0') {            ipArr[id] = 0;            backTrack(res, ipArr, s, id+1, startIndex+1);            return;        }        int sum = 0;        //这里其实就是罗列index+1,index+2,index+3三种可能ip路径并进行深度搜索，start
        
         
           0 && sum <= 255 ) { ipArr[id] = sum; backTrack(res, ipArr, s, id+1, start+1); } else { break; } } }}
         
        
       
      
     
    

 

NOTES:

1. 回溯
2. CODE1是在字符串中添加三个分割点，记录可插入的剩余分割点，每个ip段有三个可能路径队列，即[start,start+1),[start,start+2),[start,start+3),因为ip<=255,最多三位，注意临界值和索引边界判断，并在最后进行ip合不合规判断；
3. CODE2是定义一个ip数组，进行填充，记录填充的数组位置id及下一步的字符串起始索引, 填满时字符串索引也到达了最后，说明正好；以当前起始索引开始，往后解析字符串ip大小，满足区间条件进行下一位置填充；