给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: “aba”
输出: True
示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
int chance = 1;
public boolean validPalindrome(String s) {
chance = 1;
return help(s, 0, s.length() - 1);
}
boolean help(String s, int left, int right) {
for (int i = left; i < s.length(); i++) {
if (left >= right)
break;
char lc = s.charAt(i);
char rc = s.charAt(right);
if (lc == rc) {
left++;
right--;
} else {
if (chance == 0)
return false;
chance--;
boolean leftRes = help(s, left + 1, right);
boolean rightRes = help(s, left, right - 1);
return leftRes || rightRes;
}
}
return true;
}
}
|
本来想着用一个for循环处理,然后两个指针从两边往中间走,如果指向的字符不一致,则尝试移动其中一边的指针,如果移动后一致两个指针就继续一起向中间移动.提交后总有错误,我又没搞懂哪些例子会错.一气之下改成递归的,只取两边同时逼近时彻底相同的情况输出,其他情况就递归查找,然后约束一下递归次数.整体看上去给人清楚多了.