20250203力扣每日一题

解题思路

知识点

验证回文串

解决回文串问题同样可以转化成双指针问题
初始化两个指针，l指针从下标0处开始，r指针从下标str.size() - 1处开始，两个指针向中间移动
逐个判断两个指针指向的字符是否相等，直到l >= r
- 如果都相等，证明str是回文字符串
- 如果都不相等，证明str不是回文字符串

    bool checkPalindrome(const string &s, int low, int high){
        for(int i = low, j = high; i < j; ++i, --j){
            if(s[i] != s[j]){
                return false;
            }

        }
        return true;
    }

解决多一个字符的问题

在此问题中，如果碰到了两个字符不相同的问题，根据题设，我们可以删掉一个字符，分为删掉l指针指向的字符或者r指针指向的字符，这就转化为下俩问题
- 判断[l + 1, r]是不是回文串
- 判断[l, r - 1]是不是回文串
如果经过以上判断，下列两种情况可以返回true
- 原字符串本身就是回文串
- 遇到一个不相同的情况，但是[l + 1, r]或者[l, r - 1]是回文串
其余情况均返回false

实现代码

class Solution {
public:
    bool checkPalindrome(const string &s, int low, int high){
        for(int i = low, j = high; i < j; ++i, --j){
            if(s[i] != s[j]){
                return false;
            }

        }
        return true;
    }
    bool validPalindrome(string s) {
        int low = 0, high = s.size() - 1;
        while(low < high){
            char c1 = s[low], c2 = s[high];
            if(c1 == c2){
                low ++;
                high --;
            }else{
                return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
            }
        }

        return true;
    }
};

解题思路

知识点

验证回文串

解决多一个字符的问题

实现代码

Enjoy Reading This Article?