LeetCode - #93 复原 IP 地址

前言

本题由于没有合适答案为以往遗留问题，最近有时间将以往遗留问题一一完善。

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 91 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

有效 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 中的任何数字。你可以按 任何 顺序返回答案。

2. 示例

示例 1

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

示例 2

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

示例 3

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

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

3. 答案

class Solution {
    func restoreIpAddresses(_ s: String) -> [String] {
        // 所有结果
        var res = [String]()
        // 临时存放每一次的结果
        var ans = [String]()

        func validIp(_ str: String, _ start: Int) {
            // 集齐4个有效IP段， 并且后面没有更多数字了，就可加入答案
            if ans.count == 4, start >= str.count {
                res.append(ans.joined(separator: "."))
                return
            }
            
            // 每个IP段都可以是1/2/3位数字
            for j in start ... start+2 {
                // 排除越界情况
                if j > str.count-1 {
                    break
                }
                
                // -- 最恶心的是这个截取子串，不支持 Range<Int>，非要用Range<String.Index> --
                let idx0 = str.index(str.startIndex, offsetBy: start)
                let idx1 = str.index(str.startIndex, offsetBy: j)
                let substr = str[idx0 ... idx1]
                // ----------------------------------------

                // 万一题目稍微改动，不保证纯数字就不能强转，这样写更保险
                guard let num = Int(substr) else {
                    break
                }
                
                // 每一段数字只能是 0 <= x <= 255
                if num > 255 {
                    break
                }
                
                // 排除0开头的数字 如 "012"
                if substr != String(num) {
                    break
                }
                
                // 排除剩余的数字超过了所需数字上限 N*3
                if (str.count - j - 1) > (4 - ans.count)*3 {
                    continue
                }
                
                // ---- 以下是回溯套路 -----

                // 做出选择
                ans.append(String(substr))
                // 递归查找下一段
                validIp(str, j+1)
                // 撤销选择
                ans.removeLast()
            }
        }

        validIp(s, 0)
        return res
    }
}
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

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。