验证回文字符串 Ⅱ.md

验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: true

示例 2:

输入: "abca"
输出: true
解释: 你可以删除c字符。

注意:

• 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

题解

/**
 * @param {string} s
 * @param {boolean} useError 是否删除过字符
 * @return {boolean}
 */
var validPalindrome = function(s, useError) {
  if (s.length < 2) return true
  let start = 0, end = s.length - 1;
  // 一头一尾两个指针遍历
  while (start < end) {
    // 相等时缩小范围
    if (s[start] === s[end]) {
      start++
      end--
    } else if (!useError) {
      // 可删除字符时，有可能是删左边或右边的，判断剩下的是否为回文
      return validPalindrome(s.substring(start, end), true) || validPalindrome(s.substring(start + 1, end + 1), true)
    } else {
      return false
    }
  }
  return true
};