[Swift]LeetCode680.验证回文字符串Ⅱ|ValidPalindromeII

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

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

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

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

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

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

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

196ms

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3         let chars = Array(s.lowercased().unicodeScalars)
 4         
 5         var start = 0
 6         var end = chars.count - 1
 7         
 8         while start < end {
 9             if chars[start] != chars[end] {
10                 return validPalindromeRange(chars, i: start + 1, j: end) || validPalindromeRange(chars, i: start, j: end - 1)
11             }
12             
13             start += 1
14             end -= 1
15         }
16         
17         return true
18     }
19     
20     func validPalindromeRange(_ chars: [Unicode.Scalar], i: Int, j: Int) -> Bool {
21         var start = i
22         var end = j
23         
24         while start < end {
25             if chars[start] != chars[end] { return false }
26             start += 1
27             end -= 1
28         }
29         return true
30     }
31 }

200ms

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3         let array = Array(s)
 4         return isPalindrome(array, 0, array.count - 1)
 5     }
 6     
 7     fileprivate func isPalindrome(_ array: [Character], _ i: Int, _ j: Int, alreadyRemoved: Bool = false) -> Bool {
 8         var i = i, j = j
 9         while i < j {
10             if array[i] != array[j] {
11                 if alreadyRemoved {
12                     return false
13                 } else {
14                     return isPalindrome(array, i + 1, j, alreadyRemoved: true) || 
15                            isPalindrome(array, i, j - 1, alreadyRemoved: true)
16                 }
17             } else {
18                 i += 1
19                 j -= 1
20             }
21         }
22         return true
23     }
24 }

204ms

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3 
 4         var s = Array(s)
 5         var i = 0, j = s.count - 1
 6 
 7         while i < j {
 8             if s[i] == s[j] {
 9                 i += 1
10                 j -= 1
11             } else {
12                 return isValid(s, i, j - 1) || isValid(s, i + 1, j)
13             }
14         }
15 
16         return true
17     }
18 
19     func isValid(_ s: [Character], _ i: Int, _ j: Int) -> Bool {
20 
21         let mid = (i + j) / 2
22 
23         for k in i...mid {
24             if s[k] != s[j - (k - i)] {
25                 return false
26             }
27         }
28         return true
29     }
30 }

Runtime: 224 ms

Memory Usage: 20.1 MB

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3         var arr:[Character] = Array(s)
 4         var left:Int = 0
 5         var right:Int = arr.count - 1
 6         while (left < right)
 7         {
 8             if arr[left] != arr[right]
 9             {
10                  return isValid(arr, left, right - 1) || isValid(arr, left + 1, right)
11             }
12             left += 1
13             right -= 1
14         }
15         return true
16     }
17     
18     func isValid(_ arr:[Character],_ left:Int,_ right:Int) -> Bool
19     {
20         var left = left
21         var right = right
22         while (left < right)
23         {
24             if arr[left] != arr[right]
25             {
26                 return false
27             }
28             left += 1
29             right -= 1
30         }
31         return true
32     }
33 }

232ms

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3         let stringArray = Array(s.utf16)
 4         if stringArray.count == 1 || stringArray.count == 2 {return true}
 5         var i = 0
 6         var j = stringArray.count - 1
 7         var alreadyRemoved = false
 8         
 9         while i < j {
10             if stringArray[i] != stringArray[j] { 
11                 if alreadyRemoved {return false}
12                 
13                 if i+2 < j-1, stringArray[i+1] == stringArray[j],
14                 stringArray[i+2] == stringArray[j-1] {
15                     i += 1
16                     alreadyRemoved = true
17                 } else if i+2 >= j-1, stringArray[i+1] == stringArray[j] {
18                     i += 1
19                     alreadyRemoved = true
20                 } else if stringArray[i] == stringArray[j-1], stringArray[i+1] == stringArray[j-2] {
21                     j -= 1
22                     alreadyRemoved = true
23                 } else {
24                     return false
25                 }
26                 
27                 
28             }
29             i += 1
30             j -= 1        
31         }            
32         return true
33     }
34 }

244ms

 1 class Solution {
 2     func validPalindrome(_ s: String) -> Bool {
 3         return s.isPalindrome
 4     }
 5 }
 6 
 7 extension String {
 8     
 9     var isPalindrome: Bool {
10         let array = Array(self)
11         return isPalindrome(array, 0, array.count-1)
12     }
13     
14     private func isPalindrome(_ array: [Character], _ i: Int, _ j: Int, _ isAlreadyMismatched: Bool = false) -> Bool {
15         var left = i, right = j
16         while left < right {
17             if array[left] != array[right] {
18                 return isAlreadyMismatched ? false : (isPalindrome(array, left, right-1, true) || isPalindrome(array, left+1, right, true))
19             }
20             
21             left+=1
22             right-=1
23         }
24         
25         return true
26     }
27 }