Swift刷算法：复原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 中的任何数字。你可以按 任何 顺序返回答案。

LeetCode：https://leetcode.cn/problems/restore-ip-addresses

遇上字符串截取有关的算法题，Swift这个坑货真的难用，今天被坑到了😮💨

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
    }
}

image.png