[Swift]LeetCode131.分割回文串|PalindromePartitioning

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

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

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

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

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

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

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

32ms

 1 class Solution {
 2     func partition(_ s: String) -> [[String]] {
 3         var result = [[String]]()
 4         var candidate = [String]()
 5         
 6         backtracking(&result, &candidate, Array(s.characters), 0)
 7         
 8         return result
 9     }
10     
11     private func backtracking(_ result: inout [[String]], _ candidate: inout [String], _ characters: [Character], _ start: Int) {
12         if start == characters.count {
13             result.append(candidate)
14         } else {
15             for i in start..<characters.count {
16                 if isPalindrome(characters, start, i) {
17                     let character = String(characters[start...i])
18                     candidate.append(character)
19                     backtracking(&result, &candidate, characters, i + 1)
20                     candidate.removeLast()//clear every characters that fullfil requirement
21                 }
22             }
23         }
24     }
25     
26     private func isPalindrome(_ characters: [Character], _ low: Int, _ high: Int) -> Bool {
27         var low = low
28         var high = high
29         
30         while low < high {
31             if characters[low] != characters[high] {
32                 return false
33             }
34             low += 1
35             high -= 1
36         }
37         
38         return true
39     }
40 }

80ms

 1 class Solution {
 2     func isPartitionAfter(_ s:String, added:String) -> Bool {
 3     
 4     let newStr = added + s
 5     
 6     let tempStr = String(newStr.reversed())
 7     
 8     return newStr == tempStr
 9   }
10   
11         func partition(_ s: String) -> [[String]] {
12     
13     if s.isEmpty {
14       
15       return []
16     }
17     
18     if s.count == 1 {
19       
20       return [[s]]
21     }
22     
23     let first = String(s.first!)
24     
25     let startIndex = String.Index.init(encodedOffset: 1)
26     
27     let subs = partition(String(s[startIndex...]))
28     
29     var results:[[String]] = []
30     
31     for sub in subs {
32       
33       var temp = sub
34       
35       temp.insert(first, at: 0)
36       
37       results.append(temp)
38       
39       if isPartitionAfter(sub[0], added: first) {
40         
41         temp = sub
42         
43         temp[0] = first + sub[0]
44         
45         results.append(temp)
46       }
47       
48       if sub.count > 1 {
49         
50         if !isPartitionAfter(sub[0], added: sub[1]) {
51           
52           if isPartitionAfter(sub[0] + sub[1], added: first) {
53             
54             temp = sub
55             
56             temp.removeFirst()
57             
58             temp[0] = first + sub[0] + sub[1]
59             
60             results.append(temp)
61           }
62         }
63       }
64     }
65     
66     return results
67   }
68 }

656ms

 1 class Solution {
 2     func partition(_ s: String) -> [[String]] {
 3         var paths = [[String]](), path = [String]()
 4         
 5         dfs(&paths, &path, Array(s), 0)
 6         
 7         return paths
 8     }
 9     
10     fileprivate func dfs(_ paths: inout [[String]], _ path: inout [String], _ s: [Character], _ index: Int) {
11         if index == s.count {
12             paths.append(Array(path))
13             return
14         }
15         
16         for i in index..<s.count {
17             let current = String(s[index...i])
18             
19             if current.isPalindrome {
20                 path.append(current)
21                 dfs(&paths, &path, s, i + 1)
22                 path.removeLast()
23             }
24         }
25     }
26 }
27 
28 extension String {
29     var isPalindrome: Bool {
30         let chars = Array(self)
31         
32         var i = 0, j = count - 1
33         
34         while i <= j {
35             if chars[i] != chars[j] {
36                 return false
37             }
38             i += 1
39             j -= 1
40         }
41         
42         return true
43     }
44 }

1040ms

 1 class Solution {
 2     func partition(_ s: String) -> [[String]] {
 3         var result = [[String]]()
 4         helper([Character](s), [String](), &result)
 5         return result
 6     }
 7     
 8     func helper(_ chars: [Character], _ addedSub: [String], _ result: inout [[String]]) {
 9         if chars.count == 0 {
10             return
11         }
12         if chars.count == 1 {
13             var tempAddedSub = [String](addedSub)
14             tempAddedSub.append(String(chars))
15             result.append(tempAddedSub)
16             return
17         }
18         
19         let newStr = String(chars)
20         
21         if isPalindrome(newStr){
22             var tempAddedSub = [String](addedSub)
23             tempAddedSub.append(newStr)
24             result.append(tempAddedSub)
25         }
26         
27         for i in 1..<chars.count {
28             
29             let newPrefix = String(chars.prefix(upTo:i))
30             let newSuffix = [Character](chars.suffix(from:i))
31             if isPalindrome(newPrefix) {
32                 var tempAddedSub = [String](addedSub)
33                 tempAddedSub.append(newPrefix)
34                 helper([Character](newSuffix), tempAddedSub, &result)
35             }
36         }
37     }
38     
39     func isPalindrome(_ s: String) -> Bool {
40         return s == String(s.reversed())
41     }
42 }