当前位置：网站首页>剑指 Offer II 019. 最多删除一个字符得到回文（简单）

剑指 Offer II 019. 最多删除一个字符得到回文（简单）

2022-04-23 14:35:00 【重you小垃】

在这里插入图片描述
在这里插入图片描述
思路：双指针，将复杂度降到O(n)
具体思路：l=0 r=n-1 如果s[l]==s[r]则l++;r–; 否则只要s[l+1,r]或者s[l,r-1]是回文即可

class Solution {
    
public:
    bool valid(const string &s, int l, int r) {
    
        while (l < r) {
    
            if (s[l] != s[r]) return false;
            l++;r--;
        }
        return true;
    }
    bool validPalindrome(string s) {
    
 
        int l =0, r = s.size() - 1;
        while (l < r) {
    
            if (s[l] == s[r]) {
    
                l++;
                r--;
            }else {
    
                return valid(s, l + 1, r) || valid(s, l, r - 1);
            }
        }
        return true;
    }
};

版权声明
本文为[重you小垃]所创，转载请带上原文链接，感谢
https://blog.csdn.net/zhangjiaji111/article/details/124359822

边栏推荐

猜你喜欢

随机推荐