[Swift]LeetCode5. 最长回文子串 | Longest Palindromic Substring

weixin_30402085

92人浏览 · 2018-10-27 10:35:00

weixin_30402085 · 2018-10-27 10:35:00 发布

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

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)
17 
18             if resultedMax > (end - start) {
19                 start = i - (resultedMax - 1)/2
20                 end = i + resultedMax/2
21             }
22         }
23         
24         let result = String(chars[start...end])
25         print(result)
26         
27         // Return string
28         return result
29     }
30 }
31 
32 extension Array where Array.Element: Equatable {
33     func expandFromCenter(_ lhs: Int, _ rhs: Int) -> Int {
34         var left = lhs, right = rhs
35         while left >= 0, right < count, self[left] == self[right] {
36             left -= 1
37             right += 1
38         }
39         
40         return right - left - 1
41     }
42 }

152ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         let count = s.count
 4         if  count < 2{
 5             return s
 6         }
 7         
 8         var charArr = [Character]()
 9         for char in s {
10             charArr.append(char)
11         }
12         
13         var start = 0
14         var end = 0
15         for i in 0..<count {
16             var left = i
17             var right = i
18             
19             while left >= 0 && right < count && charArr[left] == charArr[right] {
20                 left -= 1
21                 right += 1
22             }
23             let len1 = right - left - 1;
24             left = i
25             right = i + 1
26             while left >= 0 && right < count && charArr[left] == charArr[right] {
27                 left -= 1
28                 right += 1
29             }
30             let len2 = right - left - 1;
31             let len = max(len1,len2)
32             if len > end - start {
33                 start = i - (len - 1) / 2
34                 end = i + len / 2
35             }
36         }
37         if start == end {
38             return String(s[s.startIndex])
39         }
40         
41         return String(s[s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: end)]);
42     }
43 }

168ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         guard s.count > 0 else {
 4             return ""
 5         }
 6         var s = Array(s)
 7         var maxLength = 0, curLength = 0
 8         var minLeft = 0, maxRight = 0
 9         var i = 0
10         let count = s.count
11         while i < count {
12             var left = i, right = i
13             while left - 1 >= 0 && s[left - 1] == s[i] {
14                 left -= 1
15             }
16             
17             while right + 1 < count && s[right + 1] == s[i] {
18                 right += 1
19             }
20             
21             while left - 1 >= 0 && right + 1 < count && s[left - 1] == s[right + 1] {
22                 left -= 1
23                 right += 1
24             }
25             curLength = right - left + 1
26             if curLength > maxLength {
27                 maxLength = curLength
28                 minLeft = left
29                 maxRight = right
30             }
31             i += 1
32         }
33         
34         var result = ""
35         for j in minLeft...maxRight {
36             result += String(s[j])
37         }
38         
39         return result
40     }
41 }

188ms

 1 class Solution {
 2   func longestPalindrome(_ s: String) -> String {
 3     if s == "" {
 4         return "";
 5     }
 6     var start = 0, end = 0
 7     var store:[Character:[Int]] = [Character:[Int]]()
 8     let lenght = s.count
 9     let chars:[Character] = [Character] (s)
10     var result = ""
11     for i in 0..<lenght {
12         let length1 = testPalindrow(chars,i,i)
13         let length2 = testPalindrow(chars,i,i+1)
14         let length = max(length1, length2)
15         if (length > end - start) {
16             start = i - (length - 1) / 2
17             end = i + length/2
18         }
19     } 
20      
21     return String(chars[start...end])
22 }
23 
24 func testPalindrow (_ s:[Character], _ left:Int, _ right:Int) -> Int {
25     var count = s.count
26     var L = left
27     var R = right
28     while (L>=0 && R < count && s[L] == s[R]) {
29         L -= 1
30         R += 1
31     }
32     return R-L-1
33 }
34 }

192ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         guard s.count > 0 else{
 4             return ""
 5         }
 6         let str_arr = Array(s)
 7         var start = 0, end = 0
 8         for i in 0..<str_arr.count{
 9             let len_one = str_arr.expandAroundCenter(lhs: i, rhs: i)
10             let len_two = str_arr.expandAroundCenter(lhs: i, rhs: i+1)
11             let len = max(len_one, len_two)
12             if len > end - start {
13                 start = i - (len - 1)/2
14                 end = i + len/2
15             }
16         }
17         let result: String = String(str_arr[start...end])
18         print(result)
19         return result
20     }
21 }

208ms

 1 class Solution {
 2     func longestPalindrome(_ s: String) -> String {
 3         if s.count <= 1 {
 4             return s
 5         }
 6         var stringArray: Array<Character> = Array(s)
 7         var maxLength: Int = 0
 8         var startIndex: Int = 0
 9         // 2 * n - 1
10         for i in 0..<2 * stringArray.count - 1 {
11             var leftIndex: Int
12             var rightIndex: Int
13             leftIndex = i / 2
14             rightIndex = (i + 1) / 2
15             while stringArray[leftIndex] == stringArray[rightIndex] {
16                 if rightIndex - leftIndex + 1 > maxLength {
17                         maxLength = rightIndex - leftIndex + 1
18                         startIndex = leftIndex
19                 }
20                 
21                 if leftIndex - 1 >= 0 && rightIndex + 1 < stringArray.count {
22                     leftIndex -= 1
23                     rightIndex += 1
24                 } else {
25                     break
26                 }
27             }
28         }
29         return String(stringArray[startIndex..<startIndex + maxLength])
30     }
31 }

2708ms：Manacher算法

 1 class Solution {
 2     //Manacher算法
 3     func longestPalindrome(_ s: String) -> String {
 4         if s == nil || s.count < 1 {return ""}
 5         else if s.count == 1{return s}
 6         var s = s
 7         //注意，为了避免更新P的时候导致越界，我们在字符串T的前增加一个特殊字符，
 8         //比如说‘$’,所以算法中字符串是从1开始的。、
 9         var manaStr = "$#"
10         for i in 0..<s.count
11         {
12             //首先构造出新的字符串
13             manaStr += String(getChar(s,i))
14             manaStr += "#"
15         }
16         //用一个辅助数组来记录最大的回文串长度，注意这里记录的是新串的长度，原串的长度要减去1
17         var rd:[Int] = [Int](repeating: 0,count: manaStr.count)
18         var pos = 0, mx = 0
19         var start = 0, maxLen = 0
20         for i in 1..<manaStr.count
21         {
22             rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1
23             //这里要注意数组越界的判断，源代码没有注意，release下没有报错
24             while(i + rd[i] < manaStr.count && i - rd[i] > 0 && getChar(manaStr,i  + rd[i]) == getChar(manaStr,i - rd[i]))
25             {
26                 rd[i] += 1
27             }
28             //如果新计算的最右侧端点大于mx,则更新pos和mx
29                   if mx < i + rd[i]
30                   {
31                 pos = i
32                 mx = i + rd[i]
33             }
34             if rd[i] - 1 > maxLen
35             {
36                 start = (i - rd[i]) / 2
37                 maxLen = rd[i] - 1
38             }
39         }
40         let index3 = s.index(s.startIndex,offsetBy:start)
41         let index4 = s.index(index3,offsetBy:maxLen - 1)
42         return String(s[index3...index4])
43     }
44         
45     func getChar(_ str:String,_ i:Int) -> Character
46     {
47         return str[str.index(str.startIndex,offsetBy:i)]
48     }
49 }