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:
- 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