680.验证回文串 II:两侧向中间,不同就试删

【LetMeFly】680.验证回文串 II:两侧向中间,不同就试删

力扣题目链接:https://leetcode.cn/problems/valid-palindrome-ii/

给你一个字符串 s最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串:如果能,返回 true ;否则,返回 false

 

示例 1:

输入:s = "aba"
输出:true

示例 2:

输入:s = "abca"
输出:true
解释:你可以删除字符 'c' 。

示例 3:

输入:s = "abc"
输出:false

 

提示:

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

解题方法:遍历

从两边到中间遍历字符串,如果当前两个字符不相同,就尝试删除其中的一个(并判断删除后中间剩下的字符串是否是回文字符串)。

如果删除一个或零个能成为回文字符串,则返回true

  • 时间复杂度$O(len(s))$
  • 空间复杂度$O(1)$

AC代码

C++

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
/*
* @Author: LetMeFly
* @Date: 2025-02-03 08:52:33
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-03 08:57:47
*/
class Solution {
private:
bool isOk(string& s, int l, int r) {
for (; l < r; l++, r--) {
if (s[l] != s[r]) {
return false;
}
}
return true;
}
public:
bool validPalindrome(string& s) {
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
return isOk(s, i, j - 1) || isOk(s, i + 1, j);
}
}
return true;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
Author: LetMeFly
Date: 2025-02-03 08:57:31
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-03 08:59:26
'''
class Solution:
def isOk(self, s: str, l: int, r: int) -> bool:
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True

def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
return self.isOk(s, l, r - 1) or self.isOk(s, l + 1, r)
l += 1
r -= 1
return True

Java

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
/*
* @Author: LetMeFly
* @Date: 2025-02-03 08:57:34
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-03 09:01:29
*/
class Solution {
private boolean isOk(String s, int l, int r) {
for (; l < r; l++, r--) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
}
return true;
}

public boolean validPalindrome(String s) {
for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
if (s.charAt(l) != s.charAt(r)) {
return isOk(s, l, r - 1) || isOk(s, l + 1, r);
}
}
return true;
}
}

Go

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
/*
* @Author: LetMeFly
* @Date: 2025-02-03 08:57:46
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-03 09:05:54
*/
package main

func isOk_VP(s string, l, r int) bool {
for ; l < r; l, r = l + 1, r - 1 {
if s[l] != s[r] {
return false
}
}
return true
}

func validPalindrome(s string) bool {
for l, r := 0, len(s) - 1; l < r; l, r = l + 1, r - 1 {
if s[l] != s[r] {
return isOk_VP(s, l, r - 1) || isOk_VP(s, l + 1, r)
}
}
return true
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/145427404

从昨天(2025.2.2)大概晚上五六点开始,又能明显感觉到great wall对github的强力封锁了。。。

其间还有对其他的强力封锁,包括我的良民小网站,使得我自己访问我自己的服务都访问不了了。

持续到昨天(2025.2.12)大概下午五点,封锁开始变弱。

6LCi6LCi5aKZ5aKZ5bim5p2l55qE4oCc6auY5pWI5byA5Y+R4oCdCg==


680.验证回文串 II:两侧向中间,不同就试删
https://blog.letmefly.xyz/2025/02/03/LeetCode 0680.验证回文串II/
作者
Tisfy
发布于
2025年2月3日
许可协议