jaryue
2023/05/08阅读:14主题:默认主题
leetcode 680. 验证回文串 II
题目描述
-
验证回文串 II
给你一个字符串 s,最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false 。
示例 1:
输入:s = "aba" 输出:true 示例 2:
输入:s = "abca" 输出:true 解释:你可以删除字符 'c' 。 示例 3:
输入:s = "abc" 输出:false
提示:
1 <= s.length <= 105 s 由小写英文字母组成
解题思路
法1
双指针+容错\
-
使用原始判断回文字符串的返回,双指针一个从头一个从尾开始遍历,直到碰头结束,判断是否为回文字符串(字符相同)
-
进阶:删除最多一个,就是可以删除一个也可以一个都不删除
-
我们就需要增加一个条件,就是删除字母的数量,如果大于一就返回假.
-
计数规则,:两个(头尾字母)字母不同时,如果移动其中一个指针可以让其相同,那么删除数量加一,如果都不行,删除数量加二(可以直接返回错误)
-
时间复杂度(O(n)) -
空间复杂度(O(1))
使用双指针 i 和 j 遍历字符串,最多需要遍历 n/2 次,其中 n 是字符串的长度。因此,时间复杂度为 O(n)。
在每次比较字符时,如果遇到不相等的字符,会调用 isPalindrome 函数判断是否可以通过删除一个字符使得剩余字符串为回文字符串。最坏情况下,需要分别检查删除左侧字符和删除右侧字符两种情况。每种情况下,需要调用 isPalindrome 函数进行判断,最多需要遍历 n/2 次。因此,时间复杂度为 O(n)。 综上,主函数的时间复杂度为 O(n)。
因此,整体代码的时间复杂度为 O(n)。空间复杂度为 O(1),因为代码只使用了常数个额外变量来存储指针位置。
执行结果
法1
func validPalindrome(s string) bool {
i := 0
j := len(s) - 1
for i < j {
if s[i] != s[j] {
// 尝试删除左侧字符或右侧字符
return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1)
}
i++
j--
}
return true
}
func isPalindrome(s string, left, right int) bool {
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 12 ms , 在所有 Go 提交中击败了 94.66% 的用户 内存消耗: 6.4 MB , 在所有 Go 提交中击败了 53.40% 的用户 通过测试用例: 469 / 469 炫耀一下:执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 12 ms , 在所有 Go 提交中击败了 94.66% 的用户 内存消耗: 6.4 MB , 在所有 Go 提交中击败了 53.40% 的用户 通过测试用例: 469 / 469 炫耀一下:
作者介绍