当前位置：网站首页>Sword finger offer II 019 Delete at most one character to get palindrome (simple)

Sword finger offer II 019 Delete at most one character to get palindrome (simple)

2022-04-23 14:40:00 【Heavy garbage】

Insert picture description here
Insert picture description here
Ideas ： Double pointer , Reduce the complexity to O(n)
Specific ideas ：l=0 r=n-1 If s[l]==s[r] be l++;r–; Otherwise, as long as s[l+1,r] perhaps s[l,r-1] It's palindrome 

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;
    }
};

版权声明
本文为[Heavy garbage]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204231435304495.html

边栏推荐

猜你喜欢

随机推荐