[Swift]LeetCode5.最长回文子串|LongestPalindromicSubstring

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

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

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

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

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

40ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         guard s.count > 0 else{
 4             return ""
 5         }
 6         guard s.count > 1 else{
 7             return s
 8         }
 9         var str_arr: [Character] = ["#"]
10         for ele in Array(s){
11             str_arr.append(ele)
12             str_arr.append("#")
13         }
14         // Array to record longest palindrome
15         var result_arr = [Int](repeating: 0, count: str_arr.count)
16         var center = 0, boundary = 0, maxLen = 0, result_center = 0
17         
18         //  首位的 "#" 不用管
19         for i in 1..<str_arr.count-1{
20             // calc mirror i = center-(i-center)
21             let iMirror = 2 * center - i
22             result_arr[i] = boundary > i ? min(boundary-i, result_arr[iMirror]) : 0
23             // Attempt to expand palindrome centered at i
24             while i-1-result_arr[i] >= 0 , i + 1 + result_arr[i] <= str_arr.count - 1, str_arr[i+1+result_arr[i]] == str_arr[i-1-result_arr[i]]{
25                 result_arr[i]+=1
26             }
27             // update center and boundary
28             // 用来记录的
29             if i + result_arr[i] > boundary{
30                 center = i
31                 boundary = i+result_arr[i]
32             }
33             // update result
34             if result_arr[i] > maxLen{
35                 maxLen = result_arr[i]
36                 result_center = i
37             }
38         }
39         let ans = String(s[s.s_index(offset: (result_center-maxLen)/2)..<s.s_index(offset: (result_center+maxLen)/2)])
40 
41         return ans
42     }
43 }
44 
45 
46 
47 extension String{
48 
49     func s_index(offset: Int) -> String.Index{
50         return self.index(self.startIndex, offsetBy: offset)
51     }
52     
53 }

44ms

 1 class Solution {
 2 func longestPalindrome(_ s: String) -> String {
 3     
 4     if s.count == 0 {
 5         return ""
 6     }
 7     
 8     if s.count == 1 {
 9         return s
10     }
11     
12     // 字符串预处理
13     var ss = [Character]()
14     for c in s {
15         ss.append("#")
16         ss.append(c)
17     }
18     ss.append("#")
19 
20     var p = Array<Int>(repeating: 0, count: s.count * 2 + 1)
21     var i = 1, mx = 0, center = 0, j = 0
22     var maxCenter = 0
23     while i < ss.count {
24         // 说明以i为中心时，已有匹配的回文字符子串
25         if mx - i > 0 {
26             // i关于对称中心id的对称点
27             j = 2 * center - i
28             p[i] = min(p[j], mx - i)
29         } else {
30             p[i] = 1
31         }
32         if i - p[i] >= 0 && i + p[i] < ss.count {
33             while ss[i - p[i]] == ss[i + p[i]] {
34                 p[i] += 1
35                 if i - p[i] < 0 || i + p[i] >= ss.count {
36                     break
37                 }
38             }
39         }
40         if p[i] + i > mx {
41             mx = p[i] + i
42             center = i
43         }
44         if p[maxCenter] < p[i] {
45             maxCenter = i
46         }
47         i += 1
48     }
49     let ret = ss[(maxCenter - p[maxCenter] + 1) ... (maxCenter + p[maxCenter] - 1)].filter { $0 != "#"}
50     return String(ret)
51 }
52 }

52ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         if s.count <= 1 {
 4             return s;
 5         }
 6         
 7         // 1.间隔之间先插入#
 8         var newString:String = "#";
 9         for var character in s {
10             newString.append(character);
11             newString = newString + "#";
12         }
13         let characters = Array(newString);
14         
15         // 2.遍历找出以每个节点作为轴最长半径
16         var maxId:Int = 0;
17         var max:Int = 0;
18         var ids:[Int] = [];
19         ids.append(1);
20         var maxLength:Int = 1;
21         var maxLengthIndex = 0;
22         
23         for var i in 1...characters.count - 1 {
24             var j:Int = maxId - (i - maxId);
25             if max > i && j >= 0 {
26                 ids.append(min(ids[j], max - i));
27             }else{
28                 ids.append(1);
29             }
30             while i + ids[i] <= characters.count - 1 && i - ids[i] >= 0 && characters[i + ids[i]] == characters[i - ids[i]]{
31                 ids[i] += 1;
32             }
33             
34             if i + ids[i] - 1 > max {
35                 maxId = i;
36                 max = i + ids[i] - 1;
37             }
38             
39             if ids[i] > maxLength{
40                 maxLength = ids[i];
41                 maxLengthIndex = i;
42             }
43         }
44         let leftIndex = s.index(s.startIndex, offsetBy: (maxLengthIndex - (maxLength - 1))/2);
45         let rightIndex = s.index(leftIndex, offsetBy:maxLength - 1 - 1);
46         return String(s[leftIndex...rightIndex]);
47     }
48 }

60ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         guard s.count > 1 else {
 4             return s
 5         }
 6         
 7         var resultLeftIndex: Int = 0
 8         var maxLen: Int = 1;
 9         
10         var sArray = Array(s)
11         
12         // 循环参数
13         var index = 0
14         
15         while index < sArray.count {
16             var leftIndex = index
17             var rightIndex = index
18             
19             // 找重复
20             while rightIndex + 1 < sArray.count && sArray[rightIndex] == sArray[rightIndex + 1] {
21                 rightIndex = rightIndex + 1
22             }
23             
24             // 下一次循环从重复数后开始继续找回文
25             index = rightIndex + 1
26             
27             // 找以left~right为中心的回文
28             while leftIndex - 1 >= 0 && rightIndex + 1 < sArray.count && sArray[leftIndex - 1] == sArray[rightIndex + 1] {
29                 leftIndex = leftIndex - 1
30                 rightIndex = rightIndex + 1
31             }
32             
33             // 判断本次回文的长度，如果最长那么记录它
34             let len: Int = rightIndex - leftIndex + 1
35             if len > maxLen {
36                 resultLeftIndex = leftIndex
37                 maxLen = len
38             }
39         }
40         
41         let nss: NSString = NSString.init(string: s)
42         
43         let result: String = nss.substring(with: NSMakeRange(resultLeftIndex, maxLen))
44         return result
45     }
46 }

64ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         if s.count <= 1 {
 4             return s;
 5         }
 6         
 7         // 1.间隔之间先插入#
 8         var newString:String = "#";
 9         for var character in s {
10             newString.append(character);
11             newString = newString + "#";
12         }
13         let characters = Array(newString);
14         
15         // 2.遍历找出以每个节点作为轴最长半径
16         var maxId:Int = 0;
17         var max:Int = 0;
18         var ids:[Int] = [];
19         ids.append(1);
20         var maxLength:Int = 1;
21         var maxLengthIndex = 0;
22         
23         for var i in 1...characters.count - 1 {
24             var j:Int = maxId - (i - maxId);
25             if max > i && j >= 0 {
26                 ids.append(min(ids[j], max - i));
27             }else{
28                 ids.append(1);
29             }
30             while i + ids[i] <= characters.count - 1 && i - ids[i] >= 0 && characters[i + ids[i]] == characters[i - ids[i]]{
31                 ids[i] += 1;
32             }
33             
34             if i + ids[i] - 1 > max {
35                 maxId = i;
36                 max = i + ids[i] - 1;
37             }
38             
39             if ids[i] > maxLength{
40                 maxLength = ids[i];
41                 maxLengthIndex = i;
42             }
43         }
44         let leftIndex = s.index(s.startIndex, offsetBy: (maxLengthIndex - (maxLength - 1))/2);
45         let rightIndex = s.index(leftIndex, offsetBy:maxLength - 1 - 1);
46         return String(s[leftIndex...rightIndex]);
47     }
48 }

76ms

 1 extension String {
 2     func getSubString(startIndex: Int, endIndex: Int) -> String {
 3         let start = self.index(self.startIndex, offsetBy: startIndex)
 4         let end = self.index(self.startIndex, offsetBy: endIndex)
 5         return String(self[start...end])
 6     }
 7     
 8     func isPalindrome() -> Bool {
 9         guard self.count >= 1 else {
10             return true
11         }
12         var amount = 0
13         let chars = self.map { String($0) }
14         for i in 0..<chars.count / 2 {
15             if chars[i] == chars[chars.count - 1 - i] {
16                 amount = amount + 1
17             }
18         }
19         return amount == chars.count / 2
20     }
21 }
22 
23 class Solution {
24 func longestPalindrome(_ s: String) -> String {
25     if s.count <= 1 {
26         return s
27     }
28     var C = 0
29     var R = 0
30 
31     let chars = s.map { String($0) }
32     var transformArr: [String] = []
33     transformArr.append("^")
34     for char in chars {
35         transformArr.append("#")
36         transformArr.append(char)
37     }
38     transformArr.append("#")
39     transformArr.append("$")
40     
41     var P = Array(repeating: 0, count: transformArr.count)
42     
43     for i in 1..<transformArr.count - 1 {
44         let i_mirror = 2 * C - i
45         if R > i {
46             P[i] = min(R - i, P[i_mirror])// 防止超出 R
47         } else {
48             P[i] = 0;// 等于 R 的情况
49         }
50         
51         while transformArr[i + 1 + P[i]] == transformArr[i - 1 - P[i]] {
52             P[i] = P[i] + 1
53         }
54         
55         if i + P[i] > R {
56             C = i
57             R = i + P[i]
58         }
59     }
60 
61     var maxLen = 0
62     var centerIndex = 0
63     for i in 1..<transformArr.count - 1 {
64         if P[i] > maxLen {
65             maxLen = P[i]
66             centerIndex = i
67         }
68     }
69     let start = (centerIndex - maxLen) / 2 //最开始讲的
70     
71     return s.getSubString(startIndex: start, endIndex: start + maxLen - 1)
72 }
73 }

96ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         guard s.count > 1 else {
 4             return s
 5         }
 6         
 7         var str = ""
 8         
 9         for i in 0..<s.count {
10             let idx = String.Index(encodedOffset: i)
11             str.append(String(s[idx]))
12             str.append("#")
13         }
14         
15         var p: [Int] = [1]
16         var ct = 0         // 中心位置
17         var mr = 1         // 回文字串的最大右边界
18         
19         var chars = [Character](str)
20         
21         
22         for i in 1..<str.count {
23             let val = mr > i ? min(p[2 * ct - i], mr-i) : 1  // p[i]的值为其对称的值p[j]和右边界到i的值的最小值
24             p.append(val)
25             
26             // 如果对称位置的字符相等则加1
27             while i-p[i] >= 0
28                 && i+p[i] < chars.count
29                 && chars[i-p[i]] == chars[i+p[i]] {
30                     p[i] += 1
31             }
32             
33             // 更新中心位置和最大右边界位置
34             if i + p[i] > mr {
35                 mr = i + p[i]
36                 ct = i
37             }
38         }
39         
40         if let val = p.max() {
41             let index = p.index(of: val)
42             let start = String.Index(encodedOffset: index!-val+1)
43             let end = String.Index(encodedOffset: index!+val)
44             return String(str[start..<end]).replacingOccurrences(of: "#", with: "")
45         }
46         
47         
48         return ""
49     }
50 }

140ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         // Base case
 4         guard s.count > 0 else { return "" }
 5         
 6         // Convert String to Array for simplicity of use
 7         let chars = Array(s)
 8         
 9         var start = 0, end = 0
10         
11         // Loop through
12         for i in 0..<chars.count {
13             let length = chars.expandFromCenter(i, i)
14             let length2 = chars.expandFromCenter(i, i + 1)
15             
16             let resultedMax = max(length, length2)
 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋