[Swift]LeetCode93.复原IP地址|RestoreIPAddresses

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

16ms

 1 class Solution {
 2     func restoreIpAddresses(_ s: String) -> [String] {
 3         if s.characters.count < 4 || s.characters.count > 12 {
 4             return []
 5         }
 6         
 7         let characters = Array(s.characters)
 8         var result = [String]()
 9         var candidate = [String]()
10         
11         backtracking(characters, 0, &candidate, &result)
12         
13         return result
14     }
15     private func backtracking(_ characters: [Character], _ pos: Int, _ candidate: inout [String], _ result: inout [String]) {
16         if candidate.count == 4 {
17             result.append(candidate.joined(separator: "."))
18             return
19         }
20         
21         let charsLeft = characters.count - pos
22         let groupsLeft = 4 - candidate.count
23         let minLen = groupsLeft == 1 ? charsLeft - groupsLeft + 1 : 1
24         let maxLen = characters[pos] == "0" ? 1 : min(3, charsLeft - groupsLeft + 1)
25         
26         if minLen > maxLen {
27             return
28         }
29 
30         for len in minLen...maxLen {
31             let num = String(characters[pos..<(pos + len)])
32             if Int(num)! > 255 {
33                 continue
34             }
35             candidate.append(num)
36             backtracking(characters, pos + len, &candidate, &result)
37             candidate.removeLast()
38         }
39     }
40 }