• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. 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字符。

注意:

  1. 字符串只包含从 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 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOS-Swift3.0-for(循环语句用法)发布时间:2022-07-13
下一篇:
[转]iOS开发系列--Swift 3.0发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap