[Swift]LeetCode214.最短回文串|ShortestPalindrome

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

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

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

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

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

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

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"

示例 2:

输入: "abcd"
输出: "dcbabcd"

52ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         let characters = Array(s)
 4         var end = s.count
 5         while true {
 6             var j = 0
 7             var i = end-1
 8             while i >= 0 {
 9                 if characters[i] == characters[j] {
10                     j += 1
11                 }
12                 i -= 1
13             }
14             if j == end {
15                 break
16             }
17             end = j
18         }
19         return (s.suffix(s.count-end).reversed() + s)
20     }
21 }

60ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         let sArray = Array(s)
 4         var j = 0
 5         for i in (0..<s.count).reversed() {
 6             if sArray[i] == sArray[j] {
 7                 j += 1
 8             }
 9         }
10         if j == s.count { return s }
11         let suffix = String(s[s.index(s.startIndex, offsetBy: j)...])
12         let prefix = suffix.reversed()
13         let mid = shortestPalindrome(String(s[s.index(s.startIndex, offsetBy:0)..<s.index(s.startIndex, offsetBy:j)]))
14         
15         return prefix + mid + suffix
16     }
17 }

68ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         return String(checkShortest(Array(s)))
 4     }
 5     
 6     func checkShortest(_ s: [Character]) -> [Character] {
 7         if s.count <= 1 {
 8             return s
 9         }
10         
11         var j = 0
12         for i in stride(from: s.count - 1, through: 0, by: -1) {
13             if s[s.index(s.startIndex, offsetBy: i)] == s[s.index(s.startIndex, offsetBy: j)] {
14                 j += 1
15             }
16         }
17         
18         if j == s.count {
19             return s
20         }
21         
22         let suffix = s[j..<s.count]
23         let middle = checkShortest(Array(s[0..<j]))
24         let prefix = suffix.reversed()
25         return prefix + middle + suffix
26     }
27 }

80ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         let sArray = Array(s)
 4         var j = 0
 5         for i in (0..<sArray.count).reversed() {
 6             if sArray[i] == sArray[j] {
 7                 j += 1
 8             }
 9         }
10         if j == sArray.count { return s }
11         let suffix = String(sArray[j...])
12         let prefix = suffix.reversed()
13         let mid = shortestPalindrome(String(sArray[0..<j]))
14         return prefix + mid + suffix
15     }
16 }

84ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         if s.isEmpty {
 4             return s
 5         }
 6         
 7         var sArr = Array(s)
 8         
 9         if sArr == sArr.reversed() {
10             return s
11         }
12         
13         var mArr = [Character]()
14         for i in 0..<sArr.count {
15             mArr.append("#")
16             mArr.append(sArr[i])
17         }
18         mArr.append("#")
19         var counts = Array(repeating: 0, count: mArr.count)
20         var right = 1
21         var center = 1
22         var left = sArr.count - 1
23         for i in 1..<mArr.count / 2 {
24             let minx = right <= i ? 1 : min(right - i, counts[center * 2 - i] + 1)
25             for r in minx...i {
26                 if mArr[i-r] != mArr[i+r] {
27                     break
28                 }
29                 counts[i] = r
30                 if i==r {
31                     left = sArr.count - i
32                 }
33             }
34             
35             if right < i + counts[i] {
36                 right = i + counts[i]
37                 center = i
38             }
39         }
40         var res = [Character]()
41         var k = sArr.count - 1
42         for _ in 0..<left {
43             res.append(sArr[k])
44             k -= 1
45         }
46         res.append(contentsOf: sArr)
47         
48         return String(res)
49     }
50 }

128ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         let characters = Array(s)
 4         var end = s.count
 5         while true {
 6             var j = 0
 7             var i = end-1
 8             while i >= 0 {
 9                 if characters[i] == characters[j] {
10                     j += 1
11                 }
12                 i -= 1
13             }
14             if j == end {
15                 break
16             }
17             end = j
18         }
19         let prefix = String(s.suffix(s.count-end).reversed())
20         return (prefix + s)
21     }
22 }

3008ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         var i:Int = 0
 4         var end:Int = s.count - 1
 5         var j:Int = end
 6         var arr:[Character] = [Character]()
 7         for char in s.characters
 8         {
 9             arr.append(char)
10         }
11         while (i < j)
12         {
13             if arr[i] == arr[j]
14             {
15                 i += 1
16                 j -= 1
17             }
18             else
19             {
20                 i = 0
21                 end -= 1
22                 j = end
23             }
24         }
25        let res:String = s.subString(end + 1).reversed() + s
26        return res
27     }
28 }
29 
30 extension String
31 {
32     // 截取字符串：从index到结束处
33     // - Parameter index: 开始索引
34     // - Returns: 子字符串
35     func subString(_ index: Int) -> String {
36         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
37         return String(self[theIndex..<endIndex])
38     }
39 }

4052ms

 1 class Solution {
 2     func shortestPalindrome(_ s: String) -> String {
 3         let characters = Array(s)
 4         let count = s.count
 5         var end = count-1
 6         while end >= 1 {
 7             if !isPalindrome(arr: characters, end: end) {
 8                 end -= 1
 9             } else {
10                 break
11             }
12         }
13         // let prefix = String(s.suffix(count-1-end).reversed())
14         return (s.suffix(count-1-end).reversed() + s)
15     }
16     
17     func isPalindrome(arr: [Character], end: Int) -> Bool {
18         for i in 0 ... end/2 {
19             let endIndex = end-i
20             if arr[i] != arr[endIndex] {
21                 return false
22             }
23         }
24         return true
25     }
26 }