这道题目是easy tag，题目让判断，在至多删除一个字符的情况下，给定的字符串是不是回文。tricky的地方是，当你发现两边字符不一样的时候，该删除左边还是右边。
e.g: "ebcbbececabbacecbbcbe", "abca"
Solution: two pointers, recursive
my solution:
class Solution {
public boolean validPalindrome(String s) {
return isValid(s, false);
}
private boolean isValid(String s, boolean flag) {
int left = 0, right = s.length() - 1;
while (left<=right) {
if(s.charAt(left) != s.charAt(right)) {
if(flag) {
return false;
} else {
flag = true;
StringBuilder sleft = new StringBuilder(s);
StringBuilder sright = new StringBuilder(s);
return isValid(sleft.deleteCharAt(left).toString(), true) || isValid(sright.deleteCharAt(right).toString(), true);
}
} else {
left++;
right--;
}
}
return true;
}
}
time complexity: O(n), recursive means touch every node once
space complexity: O(n), in this case, we only recursive at most once
网友评论