Saturday, August 1, 2020

680. Valid Palindrome II ---------E ~~~~~~~~~~~~~

Q:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

A:
这个题的核心,就是 如果两边相等,就可以直接跳过两边。  一开始自己没想到。 总想去

class Solution {
public:
    bool validPalindrome(string s) {
        int start = 0, end = s.length()-1;
        while(start<end){
            if(s[start] != s[end])
                return isPalidrome(s.substr(start,end - start)) || isPalidrome(s.substr(start+1,end - start));
            ++start;
            --end;
        }        
        return true;
    }
private:
    bool isPalidrome(string str){        
        int start = 0, end = str.length()-1;
        while(start<end){
            if(str[start] != str[end])
                return false;
            
            ++start;
            --end;
        }     
        return true;
    }
};






No comments:

Post a Comment