Leetcode (680) -- verifying palindrome string II

Leetcode（680）—— Verify palindrome string Ⅱ

subject

Given a non empty string s, Delete at most one character . Determine whether it can be a palindrome string .

Example 1：

Input : s = “aba”
Output : true

Example 2：

Input : s = “abca”
Output : true
explain : You can delete c character .

Example 3：

Input : s = “abc”
Output : false

Tips ：

• $1$ <= s.length <= $10^5$
• s It's made up of lowercase letters

Answer key

Method 1 ： greedy （ Double pointer ）

Ideas

​​   Consider the simplest approach ： First, judge whether the original string is a palindrome string , If it is , Just go back to $\text{true}$; If not , Then enumerate each location as the deleted location , Then judge whether the remaining string is a palindrome string . The incremental time complexity of this approach is $O(n^2)$ Of , Will exceed the time limit .

​​   Let's change our mind . First consider if deleting characters is not allowed , How to determine whether a string is a palindrome string . A common practice is to use double pointers . Define left and right pointers , Initially, it points to the first character and the last character of the string , Judge whether the characters pointed to by the left and right pointers are the same each time , If it's not the same , It's not a palindrome string ; If the same , Move the left and right pointers to the middle by one bit , Until the left and right pointers meet , Then the string is a palindrome string .

​​   When a maximum of one character is allowed to be deleted , You can also use double pointers , Achieve... Through greed . Initialize two pointers $\text{low}$ and $\text{high}$ Points to the first character and the last character of the string, respectively . Judge whether the characters pointed to by the two pointers are the same each time , If the same , Then update the pointer , take $\text{low}$ Add $1$,$\text{high}$ reduce $1$, Then judge whether the substring within the updated pointer range is a palindrome string . If two pointers point to different characters , Then one of the two characters must be deleted , At this point, we are divided into two situations ： That is, delete the character corresponding to the left pointer , Leave a substring $s[\text{low}+1:\text{high}]$, Or delete the character corresponding to the right pointer , Leave a substring $s[\text{low}:\text{high}-1]$. When at least one of the two substrings is a palindrome string , It means that the original string will become a palindrome string after deleting a character .

​​   The greedy strategy is ： Left and right pointers encounter different characters , Delete one of them , And then continue to traverse .

Code implementation

My own

class Solution {
    
    bool checkValidPalindrome(string& s, int l, int r){
    
        while(l < r){
    
            if(s[l] == s[r]){
    
                l++;
                r--;
            }else return false;
        }
        return true;
    }
public:
    bool validPalindrome(string s) {
    
        //  Reverse double pointer 
        int l = 0, r = s.size()-1;
        while(l < r){
    
            if(s[l] == s[r]){
    
                l++;
                r--;
            }else return checkValidPalindrome(s, l+1, r) || checkValidPalindrome(s, l, r-1);
            //  Because I'm not sure which is the string that blocks the palindrome string , So they all traverse , The wrong one will exit the function soon , It doesn't take long 
        }
        return true;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among nn Is the length of the string . The time complexity of judging whether the whole string is a palindrome string is $O(n)$, When encountering different characters , The time complexity of judging whether the two substrings are palindrome strings is also $O(n)$
Spatial complexity ：$O(1)$. You only need to maintain a limited constant space