[Swift]LeetCode516.最长回文子序列|LongestPalindromicSubsequence

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

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

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

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

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

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

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is "bb".

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:

"bbbab"

输出:

一个可能的最长回文子序列为 "bbbb"。

示例 2:
输入:

"cbbd"

输出:

一个可能的最长回文子序列为 "bb"。

280ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         let s = Array(s)
 4         guard s.count > 0 else {
 5             return 0
 6         }
 7         
 8         let len = s.count
 9         var dp = [Int](repeating: 1, count: len)
10         var i = 1
11         while i<len {
12             var maxLen = 0
13             var j = i-1
14             while j >= 0 {
15                 let previousMax = maxLen
16                 maxLen = max(dp[j], maxLen)
17                 if s[j] == s[i] {
18                     dp[j] = previousMax + 2
19                 }
20                 j-=1
21             }
22             i+=1
23         }
24         var maxLen = 1
25         for v in dp { maxLen = max(maxLen,v) }
26         return maxLen
27     }
28 }

Runtime: 292 ms

Memory Usage: 19.7 MB

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         var arr:[Character] = Array(s)
 4         var n:Int = s.count
 5         var res:Int = 0
 6         var dp:[Int] = [Int](repeating:1,count:n)
 7         for i in stride(from:n - 1,through:0,by:-1)
 8         {
 9             var len:Int = 0
10             for j in (i + 1)..<n
11             {
12                 var t:Int = dp[j]
13                 if arr[i] == arr[j]
14                 {
15                     dp[j] = len + 2
16                 }
17                 len = max(len, t)
18             }
19         }
20         return dp.max()!
21     }
22 }

300ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         let s = Array(s.utf16)
 4         guard s.count > 0 else {
 5             return 0
 6         }
 7         
 8         let count = s.count
 9         var dp = [Int](repeating: 1, count: count)
10         for j in 1..<count {
11             var temp = 0
12             var i=j-1
13             while i >= 0 {
14                 (temp, dp[i]) = (dp[i], (s[i] == s[j]) ? temp + 2 : max(dp[i], dp[i+1]))
15                 i-=1
16             }
17         }
18         return dp[0]
19     }
20 }

440ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         guard s.count > 1 else { return s.count }
 4         let chars = Array(s)
 5         
 6         var lminus2 = [Int](repeating: 0, count: s.count+1)
 7         var lminus1 = [Int](repeating: 1, count: s.count+1)
 8         var l = [Int](repeating: 0, count: s.count+1)
 9 
10         for len in (2...s.count) {
11             for start in (0..<s.count - len + 1) {
12                 if chars[start] == chars[start+len-1] {
13                     l[start] = len == 2 ? 2 : lminus2[start+1] + 2
14                 } else {
15                     l[start] = max(lminus1[start+1], lminus1[start])
16                 }
17             }
18             lminus2 = lminus1
19             lminus1 = l
20         }
21         return l[0]
22     }
23 }

768ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         let sArray = Array(s)
 4         var cache = Dictionary<State, Int>() 
 5         return countPalindrome(sArray, 0, sArray.count - 1, &cache)
 6     }
 7     
 8     private func countPalindrome(
 9         _ s: Array<Character>,
10         _ i: Int,
11         _ j: Int,
12         _ cache: inout Dictionary<State, Int>) -> Int {
13         let len = j - i + 1
14         if len == 1 {
15             return 1
16         }
17         let curEqual = s[i] == s[j]
18         guard i <= j else { return 0 }
19         let state = State(i: i, j: j)
20         guard cache[state] == nil else { return cache[state]! }
21         
22         var totalPalin = Int.min
23         if curEqual {
24          totalPalin = 2 + countPalindrome(s, i + 1, j - 1, &cache)
25         } else {
26             totalPalin = max(totalPalin, countPalindrome(s, i + 1, j, &cache))
27             totalPalin = max(totalPalin, countPalindrome(s, i, j - 1, &cache))
28         }
29         cache[state] = totalPalin
30         return totalPalin
31     }
32     
33     private struct State: Hashable {
34         var i: Int
35         var j: Int
36     }
37 }

784ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         let chars = Array(s)
 4         let N = chars.count
 5         var dp = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)
 6         var i = N-1
 7         while i >= 0 {
 8             dp[i][i] = 1
 9             for j in i+1..<N {
10                 if chars[i] == chars[j] {
11                     dp[i][j] = dp[i+1][j-1] + 2
12                 }
13                 else {
14                     dp[i][j] = max(dp[i+1][j], dp[i][j-1])
15                 }
16             }
17             i -= 1
18         }
19         return dp[0][N-1]
20     }
21 }

816ms

 1 class Solution {
 2     func longestPalindromeSubseq(_ s: String) -> Int {
 3         var dp:[[Int]] = Array(repeating: Array(repeating: 0, count: s.count), count: s.count)
 4         let arr = Array(s)
 5         for i in stride(from: arr.count - 1, to: -1, by: -1) {
 6             dp[i][i] = 1
 7             for j in i + 1..<arr.count {
 8                 if arr[i] == arr[j] {
 9                     dp[i][j] = dp[i + 1][j - 1] + 2
10                 } else {
11                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
12                 }
13             }
14         }
15         return dp[0][arr.count - 1]
16     }
17 }