LeetCode 680、验证回文串II

视频地址：LeetCode 680、验证回文串II

一、题目描述

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

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、题目解析

三、参考代码

class Solution:
    def validPalindrome(self, s: str) -> bool:

        # 判断 [ low , hight ] 这个区间的字符串是否是回文串
        def isPalindrome(low, high):

            # 左边索引的位置在 low 开始 
            left = low

            # 右边索引的位置在 high
            right = high

            # 两个索引向内移动
            # left 向右移动
            # right 向左移动
            while left < right:
                
                # 判断这两个元素值是否相同
                if s[left] != s[right]:
                    # 如果不同，直接返回 False
                    return False
                    
                # 否则，left 向右移动
                left += 1
                # right 向左移动
                right -= 1

            # 返回结果
            return True

        # 左边索引的位置在 0 开始 
        low = 0
        
        # 右边索引的位置在 len(s) - 1
        high = len(s) - 1

        # 两个索引向内移动
        # left 向右移动
        # right 向左移动
        while low < high:

            # 1、判断这两个元素值是否相同
            # 如果相同
            if s[low] == s[high]: 

                # 两个索引向内移动
                low += 1

                high -= 1

            # 2、如果不相同
            else:
                # 3、删除 low 所在这个元素，判断 [ low + 1 , high ] 是否是回文串
                # 或者
                # 4、删除 high 所在这个元素，判断 [ low  , high - 1 ] 是否是回文串
                return isPalindrome(low + 1, high) or isPalindrome(low, high - 1)
        
        # 返回结果
        return True

参考代码

#include <string>
using namespace std;

class Solution {
public:
    bool validPalindrome(string s) {

        // 判断 [ low , high ] 这个区间的字符串是否是回文串
        auto isPalindrome = [&](int low, int high) {
            // 左边索引的位置在 low 开始 
            int left = low;

            // 右边索引的位置在 high
            int right = high;

            // 两个索引向内移动
            // left 向右移动
            // right 向左移动
            while (left < right) {

                // 判断这两个元素值是否相同
                if (s[left] != s[right]) {
                    // 如果不同，直接返回 false
                    return false;
                }

                // 否则，left 向右移动
                left += 1;

                // right 向左移动
                right -= 1;
            }

            // 返回结果
            return true;
        };

        // 左边索引的位置在 0 开始 
        int low = 0;

        // 右边索引的位置在 len(s) - 1
        int high = s.size() - 1;

        // 两个索引向内移动
        // left 向右移动
        // right 向左移动
        while (low < high) {

            // 1、判断这两个元素值是否相同
            // 如果相同
            if (s[low] == s[high]) {

                // 两个索引向内移动
                low += 1;
                high -= 1;
            }

            // 2、如果不相同
            else {
                // 3、删除 low 所在这个元素，判断 [ low + 1 , high ] 是否是回文串
                // 或者
                // 4、删除 high 所在这个元素，判断 [ low , high - 1 ] 是否是回文串
                return isPalindrome(low + 1, high) || isPalindrome(low, high - 1);
            }
        }

        // 返回结果
        return true;
    }
};