剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
https://leetcode.cn/problems/RQku0D/
思路：
（1）首先判断是不是回文，然后遍历字符串，判断删除每一个字符位置后是不是回文。时间复杂度 O(n)
（2）
class Solution {
public boolean validPalindrome(String s) {
int len = s.length();
if (len <= 1) {
return true;
}
int left = 0;
int right = len - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
return isPalindrome(s, left + 1, right)
|| isPalindrome(s, left, right - 1);
}
}
return true;
}
private boolean isPalindrome(String s, int low, int high) {
for (int i = low, j = high; i < j; ++i, --j) {
char c1 = s.charAt(i), c2 = s.charAt(j);
if (c1 != c2) {
return false;
}
}
return true;
}
}
- 时间：O(n)
- 空间 ：O(1)