Valid Palindrome II
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = "aba"
Output: true
Example 2:
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Example 3:
Input: s = "abc"
Output: false
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
思路一：首先想到用删除字符的方式，遍历 [-1, s.length()] 字符位置，判断字符回文成立，结果超时了。
思路二：那就用双指针实现，因为字符串至多删除一个字符，在回文判断遇到不相等，删除字符完全分类只可能出现两种情况
- left + 1
- right - 1
要么删除左边，要么删除右边，删除字符后的字符串一定是回文
public boolean validPalindrome(String s) {
char[] chars = s.toCharArray();
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (chars[left] != chars[right]) {
return isPalindromic(chars, left+1, right) ||
isPalindromic(chars, left, right-1);
}
left++;
right--;
}
return true;
}
public boolean isPalindromic(char[] chars, int begin, int end) {
while (begin < end) {
if (chars[begin++] != chars[end--]) return false;
}
return true;
}