力扣-93.复原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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

解题思路

使用递归回溯，对字符串进行1到3个字符分隔，并进行搜索，最后筛选出满足要求的作为答案。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var restoreIpAddresses = function(s) {

    let outputArr = []
    //index当前字符串位置,selectArr已经选择的子串数组
    function recursion(index,selectArr){
        // 如果已经选择了4个子串
       if(selectArr.length == 4){
           // 如果刚好将字符串分割为4个子串，证明能复原IP地址，添加结果
            if(index == s.length)
            outputArr.push(selectArr.join('.'))
            // 如果分割后还存在字符，证明无法复原，舍去
            else return
        }
        // 如果当前索引已经超出数组范围，则直接return
        if(index >= s.length) return
        // 三种切割长度截取字符串
        for(let i = 1;i <= 3;i ++){
            // 获得三种切割长度的字符串
            let perString = s.slice(index,index+i)
            // 判断是否满足IP单个片段的要求
            if(i>1&&perString*1<256&&perString[0]!='0'||i==1)
            //满足则继续递归
            recursion(index+i,[...selectArr,perString])
        }
    }
    recursion(0,[])
    return outputArr
};