[Swift]LeetCode214. 最短回文串 | Shortest Palindrome_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: @H_502_0@ @H_502_0@

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: Output: "aacecaaa""aaacecaaa"

Example 2:

input: Output: "abcd""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 += 111                 }12                 i -= 113             }14             if j == end {15                 break16             }17             end = j18         }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 + suffix16     }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 = 012         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 += 115             }16         }17         18         if j == s.count {19             return s20         }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 + suffix26     }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 + suffix15     }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 s11         }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 = 121         var center = 122         var left = sArr.count - 123         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                     break28                 }29                 counts[i] = r30                 if i==r {31                     left = sArr.count - i32                 }33             }34             35             if right < i + counts[i] {36                 right = i + counts[i]37                 center = i38             }39         }40         var res = [Character]()41         var k = sArr.count - 142         for _ in 0..<left {43             res.append(sArr[k])44             k -= 145         }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 += 111                 }12                 i -= 113             }14             if j == end {15                 break16             }17             end = j18         }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 += 116                 j -= 117             }18             else19             {20                 i = 021                 end -= 122                 j = end23             }24         }25        let res:String = s.subString(end + 1).reversed() + s26        return res27     }28 }29 30 extension String31 {32     // 截取字符串：从index到结束处33     // - Parameter index: 开始索引34     // - Returns: 子字符串35     func subString(_ index: Int) -> String {36         let theIndex = self.index(self.en@R_404_6705@ex,offsetBy: index - self.count)37         return String(self[theIndex..<en@R_404_6705@ex])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                 break11             }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 en@R_404_6705@ex = end-i20             if arr[i] != arr[en@R_404_6705@ex] {21                 return false22             }23         }24         return true25     }26 }