### 题目

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.

### 问题分析：“核心”是固定的

##### 1. 字符串长度为“奇数”

• 多余字符在后半部分：
 核心
||
cbbcd

• 或者，多余字符在前半部分，
 核心
||
cbbcd

##### 2. 字符串长度为“偶数”

• 多余字符在后半部分：
 核心
|
cbbcbc

• 或者，多余字符在前半部分，
核心
|
cbbcbc


#### 代码

class Solution {
public boolean validPalindrome(String s) {
char[] cArr = s.toCharArray();
return isPalindrome(cArr, true) || isPalindrome(cArr, false);
}

private boolean isPalindrome(char[] arr, boolean inFirstHalf) {
int len = arr.length;
boolean ignored = false;
int lo = -2, hi = -2;
if (len % 2 == 0) { // palindrome is odd, 1 core
lo = (len - 1) / 2;
hi = lo;
} else { // palindrome is even, 2 core
lo = (len - 1) / 2 - 1;
hi = lo + 1;
}
if (inFirstHalf) {
lo++;
hi++;
}
while (lo >= 0 && hi < len) {
if (arr[lo--] != arr[hi++]) {
if (!ignored) {
if (inFirstHalf) {
hi--;
} else {
lo++;
}
ignored = true;

} else {
return false;
}
}
}
if (!ignored) {
if (inFirstHalf) {
lo--;
} else {
hi++;
}
}
return (lo == -1 && hi == len);
}
}