Easy

题目描述

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

请你判断 s 能否成为回文字符串。

如果能成为回文字符串则返回 true ，否则返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

解题思路

这道题是经典回文问题的延伸，核心思想是使用双指针技巧。

基本思路

  1. 双指针遍历：从字符串两端开始，用左右指针向中间移动
  2. 字符匹配处理：当左右字符相等时，同时移动两个指针
  3. 不匹配时的选择：当遇到不匹配字符时，我们有两种选择：
    • 删除左指针字符，检查剩余部分是否为回文
    • 删除右指针字符，检查剩余部分是否为回文
  4. 递归或辅助函数：使用辅助函数检查指定区间是否为回文

算法流程

  • 初始化左指针 left = 0，右指针 right = s.length - 1
  • 当 left < right 时循环：
    • 如果 s[left] == s[right]，两指针向中间移动
    • 如果 s[left] != s[right]，分别检查删除左字符或右字符后的子串是否为回文
  • 如果能完整遍历完成，说明原字符串本身就是回文

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                // 尝试删除左边字符或右边字符
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
        }
        return true;
    }
    
private:
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        left, right = 0, len(s) - 1
        
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                # 尝试删除左边字符或右边字符
                return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
        
        return True

public class Solution {
    public bool ValidPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        
        while (left < right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                // 尝试删除左边字符或右边字符
                return IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1);
            }
        }
        return true;
    }
    
    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

var validPalindrome = function(s) {
    const isPalindrome = (left, right) => {
        while (left < right) {
            if (s[left] !== s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    };
    
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        if (s[left]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)最坏情况下需要遍历整个字符串，其中 n 为字符串长度
空间复杂度O(1)只使用常数额外空间，不包括递归调用栈

相关题目