• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap