代码随想录

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

# 93.复原IP地址

力扣题目链接 (opens new window)

给定一个只包含数字的字符串，复原它并返回所有可能的 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"]

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

# 算法公开课

《代码随想录》算法视频公开课 (opens new window)：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址 (opens new window)，相信结合视频再看本篇题解，更有助于大家对本题的理解。

# 思路

做这道题目之前，最好先把131.分割回文串 (opens new window)这个做了。

这道题目相信大家刚看的时候，应该会一脸茫然。

其实只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串 (opens new window)就十分类似了。

切割问题可以抽象为树型结构，如图：

93.复原IP地址

# 回溯三部曲

  • 递归参数

在131.分割回文串 (opens new window)中我们就提到切割问题类似组合问题。

startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。

本题我们还需要一个变量pointNum，记录添加逗点的数量。

所以代码如下：

vector<string> result;// 记录结果
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
1
2
3
  • 递归终止条件

终止条件和131.分割回文串 (opens new window)情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。

然后验证一下第四段是否合法，如果合法就加入到结果集里

代码如下：

if (pointNum == 3) { // 逗点数量为3时，分隔结束
    // 判断第四段子字符串是否合法，如果合法就放进result中
    if (isValid(s, startIndex, s.size() - 1)) {
        result.push_back(s);
    }
    return;
}
1
2
3
4
5
6
7
  • 单层搜索的逻辑

在131.分割回文串 (opens new window)中已经讲过在循环遍历中如何截取子串。

在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环，如图中剪掉的分支：

93.复原IP地址

然后就是递归和回溯的过程：

递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。

回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。

代码如下：

for (int i = startIndex; i < s.size(); i++) {
    if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
        s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
        pointNum++;
        backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
        pointNum--;                         // 回溯
        s.erase(s.begin() + i + 1);         // 回溯删掉逗点
    } else break; // 不合法，直接结束本层循环
}
1
2
3
4
5
6
7
8
9

# 判断子串是否合法

最后就是在写一个判断段位是否是有效段位了。

主要考虑到如下三点：

  • 段位以0为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于255了不合法

代码如下：

// 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
    if (start > end) {
        return false;
    }
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
            return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

根据关于回溯算法，你该了解这些！ (opens new window)给出的回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

可以写出如下回溯算法C++代码：

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
  • 时间复杂度: O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
  • 空间复杂度: O(n)

# 总结

在131.分割回文串 (opens new window)中我列举的分割字符串的难点，本题都覆盖了。

而且本题还需要操作字符串添加逗号作为分隔符，并验证区间的合法性。

可以说是131.分割回文串 (opens new window)的加强版。

在本文的树形结构图中，我已经把详细的分析思路都画了出来，相信大家看了之后一定会思路清晰不少！

# 其他语言版本

# Java

class Solution {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return result; // 算是剪枝了
        backTrack(s, 0, 0);
        return result;
    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void backTrack(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 逗点数量为3时，分隔结束
            // 判断第四段⼦字符串是否合法，如果合法就放进result中
            if (isValid(s,startIndex,s.length()-1)) {
                result.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个逗点
                pointNum++;
                backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
                pointNum--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
            } else {
                break;
            }
        }
    }

    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
}
//方法一：但使用stringBuilder，故优化时间、空间复杂度，因为向字符串插入字符时无需复制整个字符串，从而减少了操作的时间复杂度，也不用开新空间存subString，从而减少了空间复杂度。
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return result;
    }
    private void backTracking(StringBuilder s, int startIndex, int dotCount){
        if(dotCount == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s.toString());
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    //[start, end]
    private boolean isValid(StringBuilder s, int start, int end){
        if(start > end)
            return false;
        if(s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255)
                return false;
        }
        return true;
    }
}

//方法二：比上面的方法时间复杂度低，更好地剪枝，优化时间复杂度
class Solution {
    List<String> result = new ArrayList<String>();
	StringBuilder stringBuilder = new StringBuilder();

	public List<String> restoreIpAddresses(String s) {
		restoreIpAddressesHandler(s, 0, 0);
		return result;
	}

	// number表示stringbuilder中ip段的数量
	public void restoreIpAddressesHandler(String s, int start, int number) {
		// 如果start等于s的长度并且ip段的数量是4，则加入结果集，并返回
		if (start == s.length() && number == 4) {
			result.add(stringBuilder.toString());
			return;
		}
		// 如果start等于s的长度但是ip段的数量不为4，或者ip段的数量为4但是start小于s的长度，则直接返回
		if (start == s.length() || number == 4) {
			return;
		}
		// 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
		for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0
				&& Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {
			if (i + 1 - start > 1 && s.charAt(start) - '0' == 0) {
				break;
			}
			stringBuilder.append(s.substring(start, i + 1));
			// 当stringBuilder里的网段数量小于3时，才会加点；如果等于3，说明已经有3段了，最后一段不需要再加点
			if (number < 3) {
				stringBuilder.append(".");
			}
			number++;
			restoreIpAddressesHandler(s, i + 1, number);
			number--;
			// 删除当前stringBuilder最后一个网段，注意考虑点的数量的问题
			stringBuilder.delete(start + number, i + number + 2);
		}
	}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

# Python

回溯（版本一）

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        self.backtracking(s, 0, 0, "", result)
        return result

    def backtracking(self, s, start_index, point_num, current, result):
        if point_num == 3:  # 逗点数量为3时，分隔结束
            if self.is_valid(s, start_index, len(s) - 1):  # 判断第四段子字符串是否合法
                current += s[start_index:]  # 添加最后一段子字符串
                result.append(current)
            return

        for i in range(start_index, len(s)):
            if self.is_valid(s, start_index, i):  # 判断 [start_index, i] 这个区间的子串是否合法
                sub = s[start_index:i + 1]
                self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)
            else:
                break

    def is_valid(self, s, start, end):
        if start > end:
            return False
        if s[start] == '0' and start != end:  # 0开头的数字不合法
            return False
        num = 0
        for i in range(start, end + 1):
            if not s[i].isdigit():  # 遇到非数字字符不合法
                return False
            num = num * 10 + int(s[i])
            if num > 255:  # 如果大于255了不合法
                return False
        return True
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
29
30
31
32
33
34

回溯（版本二）

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        results = []
        self.backtracking(s, 0, [], results)
        return results

    def backtracking(self, s, index, path, results):
        if index == len(s) and len(path) == 4:
            results.append('.'.join(path))
            return

        if len(path) > 4:  # 剪枝
            return

        for i in range(index, min(index + 3, len(s))):
            if self.is_valid(s, index, i):
                sub = s[index:i+1]
                path.append(sub)
                self.backtracking(s, i+1, path, results)
                path.pop()

    def is_valid(self, s, start, end):
        if start > end:
            return False
        if s[start] == '0' and start != end:  # 0开头的数字不合法
            return False
        num = int(s[start:end+1])
        return 0 <= num <= 255

回溯（版本三）

```python
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        self.backtracking(s, 0, [], result)
        return result
    
    def backtracking(self, s, startIndex, path, result):
        if startIndex == len(s):
            result.append('.'.join(path[:]))
            return
        
        for i in range(startIndex, min(startIndex+3, len(s))):
            # 如果 i 往后遍历了，并且当前地址的第一个元素是 0 ，就直接退出
            if i > startIndex and s[startIndex] == '0':
                break
            # 比如 s 长度为 5，当前遍历到 i = 3 这个元素
            # 因为还没有执行任何操作，所以此时剩下的元素数量就是 5 - 3 = 2 ，即包括当前的 i 本身
            # path 里面是当前包含的子串，所以有几个元素就表示储存了几个地址
            # 所以 (4 - len(path)) * 3 表示当前路径至多能存放的元素个数
            # 4 - len(path) 表示至少要存放的元素个数
            if (4 - len(path)) * 3 < len(s) - i or 4 - len(path) > len(s) - i:
                break
            if i - startIndex == 2:
                if not int(s[startIndex:i+1]) <= 255:
                    break
            path.append(s[startIndex:i+1])
            self.backtracking(s, i+1, path, result)
            path.pop()
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

# Go

var (
    path []string
    res  []string
)
func restoreIpAddresses(s string) []string {
    path, res = make([]string, 0, len(s)), make([]string, 0)
    dfs(s, 0)
    return res
}
func dfs(s string, start int) {  
    if len(path) == 4 {    // 够四段后就不再继续往下递归
        if start == len(s) {      
            str := strings.Join(path, ".")
            res = append(res, str)
        }
        return 
    }
    for i := start; i < len(s); i++ {
        if i != start && s[start] == '0' { // 含有前导 0，无效
            break
        }
        str := s[start : i+1]
        num, _ := strconv.Atoi(str)
        if num >= 0 && num <= 255 {
            path = append(path, str)  // 符合条件的就进入下一层
            dfs(s, i+1)
            path = path[:len(path) - 1]
        } else {   // 如果不满足条件，再往后也不可能满足条件，直接退出
            break
        }
    }
}
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
29
30
31
32

# JavaScript

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const res = [], path = [];
    backtracking(0, 0)
    return res;
    function backtracking(i) {
        const len = path.length;
        if(len > 4) return;
        if(len === 4 && i === s.length) {
            res.push(path.join("."));
            return;
        }
        for(let j = i; j < s.length; j++) {
            const str = s.slice(i, j + 1);
            if(str.length > 3 || +str > 255) break;
            if(str.length > 1 && str[0] === "0") break;
            path.push(str);
            backtracking(j + 1);
            path.pop()
        }
    }
};
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

# TypeScript

function isValidIpSegment(str: string): boolean {
    let resBool: boolean = true;
    let tempVal: number = Number(str);
    if (
        str.length === 0 || isNaN(tempVal) ||
        tempVal > 255 || tempVal < 0 ||
        (str.length > 1 && str[0] === '0')
    ) {
        resBool = false;
    }
    return resBool;
}
function restoreIpAddresses(s: string): string[] {
    const resArr: string[] = [];
    backTracking(s, 0, []);
    return resArr;
    function backTracking(s: string, startIndex: number, route: string[]): void {
        let length: number = s.length;
        if (route.length === 4 && startIndex >= length) {
            resArr.push(route.join('.'));
            return;
        }
        if (route.length === 4 || startIndex >= length) return;
        let tempStr: string = '';
        for (let i = startIndex + 1; i <= Math.min(length, startIndex + 3); i++) {
            tempStr = s.slice(startIndex, i);
            if (isValidIpSegment(tempStr)) {
                route.push(s.slice(startIndex, i));
                backTracking(s, i, route);
                route.pop();
            }
        }
    }
};
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
29
30
31
32
33
34

# Rust

impl Solution {
    fn is_valid(s: &[char], start: usize, end: usize) -> bool {
        if start > end {
            return false;
        }
        if s[start] == '0' && start != end {
            return false;
        }
        let mut num = 0;
        for &c in s.iter().take(end + 1).skip(start) {
            if !('0'..='9').contains(&c) {
                return false;
            }
            if let Some(digit) = c.to_digit(10) {
                num = num * 10 + digit;
            }
            if num > 255 {
                return false;
            }
        }
        true
    }

    fn backtracking(result: &mut Vec<String>, s: &mut Vec<char>, start_index: usize, mut point_num: usize) {
        let len = s.len();
        if point_num == 3 {
            if Self::is_valid(s, start_index, len - 1) {
                result.push(s.iter().collect::<String>());
            }
            return;
        }
        for i in start_index..len {
            if Self::is_valid(s, start_index, i) {
                point_num += 1;
                s.insert(i + 1, '.');
                Self::backtracking(result, s, i + 2, point_num);
                point_num -= 1;
                s.remove(i + 1);
            }   else { break; }
        }
    }

    pub fn restore_ip_addresses(s: String) -> Vec<String> {
        let mut result: Vec<String> = Vec::new();
        let len = s.len();
        if len < 4 || len > 12 { return result; }
        let mut s = s.chars().collect::<Vec<char>>();
        Self::backtracking(&mut result, &mut s, 0, 0);
        result
    }

}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# C

//记录结果
char** result;
int resultTop;
//记录应该加入'.'的位置
int segments[3];
int isValid(char* s, int start, int end) {
    if(start > end)
        return 0;
    if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
    }
    int num = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
            return false;
        }
        num = num * 10 + (s[i] - '0');
        if (num > 255) { // 如果大于255了不合法
            return false;
        }
    }
    return true;
}

//startIndex为起始搜索位置，pointNum为'.'对象
void backTracking(char* s, int startIndex, int pointNum) {
    //若'.'数量为3，分隔结束
    if(pointNum == 3) {
        //若最后一段字符串符合要求，将当前的字符串放入result种
        if(isValid(s, startIndex, strlen(s) - 1)) {
            char* tempString = (char*)malloc(sizeof(char) * strlen(s) + 4);
            int j;
            //记录添加字符时tempString的下标
            int count = 0;
            //记录添加字符时'.'的使用数量
            int count1 = 0;
            for(j = 0; j < strlen(s); j++) {
                tempString[count++] = s[j];
                //若'.'的使用数量小于3且当前下标等于'.'下标，添加'.'到数组
                if(count1 < 3 && j == segments[count1]) {
                    tempString[count++] = '.';
                    count1++;
                }
            }
            tempString[count] = 0;
            //扩容result数组
            result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));
            result[resultTop++] = tempString;
        }
        return ;
    }

    int i;
    for(i = startIndex; i < strlen(s); i++) {
        if(isValid(s, startIndex, i)) {
            //记录应该添加'.'的位置
            segments[pointNum] = i;
            backTracking(s, i + 1, pointNum + 1);
        }
        else {
            break;
        }
    }
}

char ** restoreIpAddresses(char * s, int* returnSize){
    result = (char**)malloc(0);
    resultTop = 0;
    backTracking(s, 0, 0);
    *returnSize = resultTop;
    return result;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# Swift

// 判断区间段是否合法
func isValid(s: [Character], start: Int, end: Int) -> Bool {
    guard start <= end, start >= 0, end < s.count else { return false } // 索引不合法
    if start != end, s[start] == "0" { return false } // 以0开头的多位数字不合法
    var num = 0
    for i in start ... end {
        let c = s[i]
        guard c >= "0", c <= "9" else { return false } // 非数字不合法
        let value = c.asciiValue! - ("0" as Character).asciiValue!
        num = num * 10 + Int(value)
        guard num <= 255 else { return false } // 大于255不合法
    }
    return true
}
func restoreIpAddresses(_ s: String) -> [String] {
    var s = Array(s) // 转换成字符数组以便于比较
    var result = [String]() // 结果
    func backtracking(startIndex: Int, pointCount: Int) {
        guard startIndex < s.count else { return } // 索引不合法
        // 结束条件
        if pointCount == 3 {
            // 最后一段也合法，则收集结果
            if isValid(s: s, start: startIndex, end: s.count - 1) {
                result.append(String(s))
            }
            return
        }

        for i in startIndex ..< s.count {
            // 判断[starIndex, i]子串是否合法，合法则插入“.”，否则结束本层循环
            if isValid(s: s, start: startIndex, end: i) {
                s.insert(".", at: i + 1) // 子串后面插入“.”
                backtracking(startIndex: i + 2, pointCount: pointCount + 1) // 注意这里时跳2位，且通过pointCount + 1局部变量隐藏了pointCount的回溯
                s.remove(at: i + 1) // 回溯
            } else {
                break
            }
        }
    }
    backtracking(startIndex: 0, pointCount: 0)
    return result
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# Scala

object Solution {
  import scala.collection.mutable
  def restoreIpAddresses(s: String): List[String] = {
    var result = mutable.ListBuffer[String]()
    if (s.size < 4 || s.length > 12) return result.toList
    var path = mutable.ListBuffer[String]()

    // 判断IP中的一个字段是否为正确的
    def isIP(sub: String): Boolean = {
      if (sub.size > 1 && sub(0) == '0') return false
      if (sub.toInt > 255) return false
      true
    }

    def backtracking(startIndex: Int): Unit = {
      if (startIndex >= s.size) {
        if (path.size == 4) {
          result.append(path.mkString(".")) // mkString方法可以把集合里的数据以指定字符串拼接
          return
        }
        return
      }
      // subString
      for (i <- startIndex until startIndex + 3 if i < s.size) {
        var subString = s.substring(startIndex, i + 1)
        if (isIP(subString)) { // 如果合法则进行下一轮
          path.append(subString)
          backtracking(i + 1)
          path = path.take(path.size - 1)
        }
      }
    }

    backtracking(0)
    result.toList
  }
}
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
29
30
31
32
33
34
35
36
37

# C#

public class Solution
{
    public IList<string> res = new List<string>();
    public IList<string> RestoreIpAddresses(string s)
    {
        if (s.Length < 4 || s.Length > 12) return res;
        BackTracking(s, 0, 0);
        return res;
    }
    public void BackTracking(string s, int start, int pointSum)
    {
        if (pointSum == 3)
        {
            if (IsValid(s, start, s.Length - 1))
            {
                res.Add(s);
            }
            return;
        }
        for (int i = start; i < s.Length; i++)
        {
            if (IsValid(s, start, i))
            {
                s = s.Insert(i + 1, ".");
                BackTracking(s, i + 2, pointSum + 1);
                s = s.Remove(i + 1, 1);
            }
            else break;
        }
    }
    public bool IsValid(string s, int start, int end)
    {
        if (start > end) return false;
        if (s[start] == '0' && start != end) return false;
        int num = 0;
        for (int i = start; i <= end; i++)
        {
            if (s[i] > '9' || s[i] < '0') return false;
            num = num * 10 + s[i] - '0';
            if (num > 255) return false;
        }
        return true;
    }
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
上次更新：: 8/29/2024, 9:07:04 PM

← 11. 子集问题 →

@2021-2024 代码随想录 版权所有 粤ICP备19156078号