https://leetcode.com/problems/restore-ip-addresses/

先使用方法intToType算出给定一个字符串能够组成ip的所有排列组合比如[2,3,2,3]代表按这样的形式分割字符串生成ip。可以看到我的方法已经穷举了所有可能,default里面也有对应的算法,只是穷举出来速度更快,大概提高了13%。因为这里场景范围比较小,将每个值带入就可以穷举出值。现在的算法还有几个可以优化的地方。比如知道第一位不为一个长度为3的字符串之后,后续的第一个就可以排除长度为3的。

class Solution {
    func restoreIpAddresses(_ s: String) -> [String] {
        guard s.count <= 12 && s.count >= 4 else { return [] }
        var res = [String]()
        for item in intToType(s.count) {
            var i = s.startIndex
            var j = s.startIndex
            var b = true
            var sub = ""
            for range in item {
                j = s.index(i, offsetBy: range)
                let subString = String(s[i..<j])
                guard !(subString.starts(with: "0") &&  subString.count > 1) else {
                    b = false
                    break
                }
                if let num = Int(subString), num < 256 {
                    sub += subString + "."
                    i = j
                    continue
                } else {
                    b = false
                    break
                }
            }
            if b {
                sub.removeLast()
                res.append(sub)
            }
        }
        return res
    }

    func intToType(_ i: Int) -> Set<Array<Int>> {
        switch i {
        case 4:
            return [[1,1,1,1]]
        case 5:
            return [[2,1,1,1],[1,2,1,1],[1,1,2,1],[1,1,1,2]]
        case 6:
            return [[2, 2, 1, 1], [1, 1, 2, 2], [2, 1, 1, 2], [1, 3, 1, 1], [1, 2, 1, 2], [2, 1, 2, 1], [1, 1, 3, 1], [3, 1, 1, 1], [1, 2, 2, 1], [1, 1, 1, 3]]
        case 7:
            return [[2, 1, 3, 1], [1, 1, 3, 2], [1, 1, 2, 3], [4, 1, 1, 1], [1, 1, 1, 4], [1, 4, 1, 1], [2, 3, 1, 1], [3, 1, 2, 1], [2, 1, 1, 3], [1, 3, 2, 1], [2, 2, 1, 2], [1, 3, 1, 2], [1, 2, 3, 1], [1, 1, 4, 1], [1, 2, 1, 3], [3, 1, 1, 2], [2, 1, 2, 2], [1, 2, 2, 2], [2, 2, 2, 1], [3, 2, 1, 1]]
        case 8:
            return [[1, 1, 5, 1], [1, 1, 3, 3], [2, 1, 2, 3], [1, 4, 1, 2], [1, 2, 4, 1], [3, 1, 3, 1], [2, 4, 1, 1], [1, 2, 2, 3], [1, 3, 3, 1], [1, 4, 2, 1], [4, 1, 2, 1], [1, 1, 2, 4], [3, 2, 1, 2], [4, 2, 1, 1], [2, 3, 1, 2], [1, 1, 1, 5], [4, 1, 1, 2], [1, 1, 4, 2], [2, 2, 1, 3], [1, 3, 1, 3], [2, 1, 4, 1], [1, 5, 1, 1], [1, 3, 2, 2], [5, 1, 1, 1], [2, 1, 1, 4], [1, 2, 3, 2], [2, 1, 3, 2], [3, 2, 2, 1], [3, 1, 2, 2], [2, 3, 2, 1], [3, 3, 1, 1], [2, 2, 2, 2], [1, 2, 1, 4], [3, 1, 1, 3], [2, 2, 3, 1]]
        case 9:
            return [[2, 3, 1, 3], [3, 4, 1, 1], [2, 3, 2, 2], [1, 2, 1, 5], [5, 2, 1, 1], [4, 2, 1, 2], [1, 4, 3, 1], [1, 5, 1, 2], [5, 1, 1, 2], [1, 3, 4, 1], [2, 2, 4, 1], [2, 1, 2, 4], [2, 3, 3, 1], [2, 1, 3, 3], [3, 1, 1, 4], [1, 2, 4, 2], [3, 2, 2, 2], [2, 2, 3, 2], [3, 3, 2, 1], [2, 1, 4, 2], [6, 1, 1, 1], [3, 1, 2, 3], [2, 4, 2, 1], [3, 3, 1, 2], [3, 1, 4, 1], [4, 1, 3, 1], [3, 2, 1, 3], [1, 4, 1, 3], [1, 1, 6, 1], [2, 1, 1, 5], [1, 2, 3, 3], [4, 1, 1, 3], [1, 1, 1, 6], [1, 2, 5, 1], [2, 5, 1, 1], [1, 1, 5, 2], [1, 4, 2, 2], [4, 3, 1, 1], [4, 2, 2, 1], [2, 2, 1, 4], [1, 2, 2, 4], [1, 5, 2, 1], [5, 1, 2, 1], [2, 2, 2, 3], [1, 3, 1, 4], [1, 1, 3, 4], [1, 3, 3, 2], [3, 1, 3, 2], [1, 1, 2, 5], [2, 1, 5, 1], [1, 1, 4, 3], [2, 4, 1, 2], [3, 2, 3, 1], [1, 6, 1, 1], [4, 1, 2, 2], [1, 3, 2, 3]]
        case 10:
            return [[2, 3, 3, 2], [2, 3, 4, 1], [1, 6, 2, 1], [2, 4, 1, 3], [4, 2, 2, 2], [1, 2, 2, 5], [5, 2, 1, 2], [4, 2, 3, 1], [3, 4, 2, 1], [1, 3, 4, 2], [3, 1, 2, 4], [1, 1, 5, 3], [1, 2, 5, 2], [2, 6, 1, 1], [5, 1, 1, 3], [1, 1, 2, 6], [2, 2, 4, 2], [1, 2, 3, 4], [3, 1, 3, 3], [3, 2, 2, 3], [2, 1, 5, 2], [3, 2, 1, 4], [2, 2, 2, 4], [4, 1, 2, 3], [4, 1, 3, 2], [2, 2, 3, 3], [3, 5, 1, 1], [3, 1, 1, 5], [2, 1, 4, 3], [1, 1, 6, 2], [2, 1, 1, 6], [3, 2, 4, 1], [6, 2, 1, 1], [1, 1, 7, 1], [4, 1, 4, 1], [2, 1, 3, 4], [4, 2, 1, 3], [6, 1, 2, 1], [1, 5, 2, 2], [4, 4, 1, 1], [1, 3, 2, 4], [1, 3, 1, 5], [1, 7, 1, 1], [1, 4, 2, 3], [3, 1, 4, 2], [2, 4, 2, 2], [3, 3, 1, 3], [6, 1, 1, 2], [1, 2, 6, 1], [5, 2, 2, 1], [1, 3, 3, 3], [5, 1, 2, 2], [4, 3, 1, 2], [1, 4, 4, 1], [2, 2, 5, 1], [2, 1, 6, 1], [1, 1, 4, 4], [3, 3, 3, 1], [1, 5, 1, 3], [1, 3, 5, 1], [2, 5, 1, 2], [3, 2, 3, 2], [1, 2, 4, 3], [5, 1, 3, 1], [2, 1, 2, 5], [4, 1, 1, 4], [3, 1, 5, 1], [3, 4, 1, 2], [2, 3, 1, 4], [1, 4, 3, 2], [1, 2, 1, 6], [2, 5, 2, 1], [1, 5, 3, 1], [2, 3, 2, 3], [4, 3, 2, 1], [7, 1, 1, 1], [1, 1, 1, 7], [2, 2, 1, 5], [1, 6, 1, 2], [1, 1, 3, 5], [3, 3, 2, 2], [5, 3, 1, 1], [2, 4, 3, 1], [1, 4, 1, 4]]
        case 11:
            return [[3,3,3,2],[3,3,2,3],[3,2,3,3],[2,3,3,3]]
        case 12:
            return [[3,3,3,3]]
        default:
            var res = Set<Array<Int>>()
            for item in Array(intToType(i-1)) {
                for j in 0..<4 {
                    var newItem = item
                    newItem[j] += 1
                    res.insert(newItem)
                }
            }
            return res
        }
    }
}

Runtime: 20 ms, faster than 86.67% of Swift online submissions for Restore IP Addresses.
Memory Usage: 20.1 MB, less than 33.33% of Swift online submissions for Restore IP Addresses.