Description
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.
Solution
Two-pointer, time O(n), space O(1)
这道题跟“665. Non-decreasing Array”有异曲同工之妙。
遇到不回文的位置i和j时，要么删掉i处字符，要么删掉j处字符，看剩余字符是否回文即可。
class Solution {
public boolean validPalindrome(String s) {
return dfs(s, 0, s.length() - 1, 1);
}
private boolean dfs(String s, int start, int end, int k) {
if (start >= end) {
return true;
}
while (start < end && s.charAt(start) == s.charAt(end)) {
++start;
--end;
}
if (start >= end) {
return true;
} else if (k > 0) {
return dfs(s, start + 1, end, k - 1) || dfs(s, start, end - 1, k - 1);
} else {
return false;
}
}
}
