剑指 Offer II 019. 最多删除一个字符得到回文
题目
给定一个非空字符串s,请判断如果最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
输入: s = “aba”
输出: true
示例 2:
输入: s = “abca”
输出: true
解释: 可以删除 “c” 字符 或者 “b” 字符
示例 3:
输入: s = “abc”
输出: false
提示:
- 1 <= s.length <= 105
- s 由小写英文字母组成
注意:本题与主站680题相同
题解
public boolean validPalindrome(String s) {
BiFunction<String, Boolean, Boolean> isPalindrome = new BiFunction<String, Boolean, Boolean>() {
@Override
public Boolean apply(String t, Boolean f) {
int len = t.length(), mid = len >> 1, left = 0;
while (left < mid) {
if (t.charAt(left) != t.charAt(len - left - 1)) {
// 只允许删除一个字符
if (!f) {
return false;
}
return
// 删除右边字符
this.apply(t.substring(left, len - left - 1), false)
// 删除左边字符
|| this.apply(t.substring(left + 1, len - left), false);
}
left++;
}
return true;
}
};
return isPalindrome.apply(s, true);
}