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; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
[…] Reference:http://zxi.mytechroad.com/blog/string/leetcode-680-valid-palindrome-ii/ […]