[Swift]LeetCode132.分割回文串II|PalindromePartitioningII

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›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 the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

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

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

148ms

 1 class Solution {
 2     func minCut(_ s: String) -> Int {
 3         var isPalindrome = Array(repeating: Array(repeating: false, count: s.count), count: s.count)
 4         var res = Array(repeating: Int.max, count: s.count)
 5         let sArray = Array(s)
 6         
 7         for i in 0..<s.count {
 8             for j in 0..<i + 1 {
 9                 if sArray[j] == sArray[i] && (i - j < 2 || isPalindrome[j + 1][i - 1]) {
10                     res[i] = j == 0 ? 0 : min(res[i], res[j - 1] + 1)
11                     isPalindrome[j][i] = true
12                 }
13             }
14         }
15         
16         return res[res.count - 1]
17     }
18 }

148ms

 1 class Solution {
 2     func minCut(_ s: String) -> Int {
 3         if s.isEmpty {
 4             return 0
 5         }
 6         
 7         let count = s.count
 8         var nums = Array(repeating: 0, count: count+1)
 9         for i in 0...count {
10             nums[i] = count - i - 1
11         }
12         var p = Array(repeating: Array(repeating: false, count: count), count: count)
13         let sArr = Array(s)
14         
15         for i in stride(from: count-1, to: -1, by: -1) {
16             for j in i..<count {
17                 if sArr[i] == sArr[j] && (j-i<=1 || p[i+1][j-1]) {
18                     p[i][j] = true
19                     nums[i] = min(nums[i], nums[j+1] + 1)
20                 }
21             }
22         }
23         
24         
25         return nums[0]
26     }
27 }

156ms

 1 class Solution {
 2     func minCut(_ s: String) -> Int {
 3 
 4         var n = s.count
 5         guard n > 1 else { return 0 }
 6         let s = Array(s)
 7         var p = Array(repeating: Array(repeating: false, count: n), count: n )
 8         var dp = [Int]()
 9         for i in 0...n { dp.append(n-i-1) }
10         for i in (0...n-1).reversed() {
11             for j in i...n-1 {
12                 if s[i] == s[j], (j-i <= 1 || p[i+1][j-1]) {
13                     p[i][j] = true
14                     dp[i] = min(dp[i], dp[j+1]+1)
15                 }
16             }
17         }
18         return dp[0]
19     }
20 }

172ms

 1 class Solution {
 2     func minCut(_ s: String) -> Int {
 3         var res = [Int](repeating: Int.max, count: s.count)
 4         var isPalindrome = Array(repeating: Array(repeating: false, count: s.count), count: s.count)
 5         let sArray = Array(s)
 6         
 7         for i in 0..<s.count {
 8             for j in 0..<i + 1 {
 9                 if sArray[i] == sArray[j] && (i - j < 2 || isPalindrome[j + 1][i - 1]) {
10                     res[i] = j == 0 ? 0 : min(res[i], res[j - 1] + 1)
11                     isPalindrome[j][i] = true
12                 }
13             }
14         }
15         
16         return res[res.count - 1]
17     }
18 }