LeetCode 680. 验证回文串 II
题目描述
思路分析
我们可以使用双指针的方法来解决这个问题。
- 首先定义两个指针，分别指向字符串的开头和结尾。
- 然后逐步向中间移动指针，比较指向的字符。
- 如果字符相同，则继续移动指针；
- 如果字符不同，则可以选择删除一个字符，分别尝试删除左指针或右指针指向的字符，检查剩余的子字符串是否为回文。
参考代码
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
func validPalindrome(s string) bool {
// 判断是否是回文串
isPalindrome := func(s string) bool {
left, right := 0, len(s)-1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
// 双指针法
left, right := 0, len(s)-1
for left < right {
if s[left] != s[right] {
// 如果不相等，检查去掉左边或右边字符后的子串是否是回文
return isPalindrome(s[left+1:right+1]) || isPalindrome(s[left:right])
}
left++
right--
}
return true
}
- 时间复杂度：O (n)，其中 n 是字符串的长度。我们最多遍历字符串两次。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！