当前位置：首页 > article >正文

LeetCode 0680.验证回文串 II：两侧向中间，不同就试删

article 2025/2/4 16:05:00

【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 <= 10⁵
s 由小写英文字母组成

解题方法：遍历

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

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

时间复杂度 $O (l e n (s))$
空间复杂度 $O (1)$

AC代码

C++

/*
 * @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

'''
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

/*
 * @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

/*
 * @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
}