Problem:
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
|
1 2 |
Input: "aba" Output: True |
Example 2:
|
1 2 3 |
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.
Idea:
Greedy, delete the first unmatched char
Time complexity
O(n)
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 118 ms class Solution { public: bool validPalindrome(const string& s) { int l = -1; int r = s.length(); while (++l < --r) if (s[l] != s[r]) return isPalindrome(s, l+1, r) || isPalindrome(s, l, r-1); return true; } private: bool isPalindrome(const string& s, int l, int r) { while (l < r) if (s[l++] != s[r--]) return false; return true; } }; |