680. 验证回文字符串-2(Easy)
# 题目描述
给定一个非空字符串 s
,最多删除一个字符。判断是否能成为回文字符串。
# 样例
Input: "aba"
Output: True
Input: "abca"
Output: True
# 删除 c
1
2
3
4
5
6
2
3
4
5
6
# 题解
双指针搜索,中间加上了一项条件的判断
# Python示例
class Solution:
def validPalindrome(self, s: str) -> bool:
def checkPalindrom(l, r):
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] == s[r]:
l += 1
r -= 1
else:
return checkPalindrom(l+1, r) or checkPalindrom(l, r-1)
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Go 示例
func isPalindrome(s string, i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
func validPalindrome(s string) bool {
if len(s) == 0 || len(s) == 1 {
return true
}
for i, j:= 0, len(s) - 1; i < j;{
if s[i] == s[j] {
i++
j--
} else {
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1)
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54