剑指 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);
}