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 }