Lt680. 验证回文字符串 Ⅱ

680. 验证回文字符串 Ⅱ

难度简单 324 收藏分享切换为英文接收动态反馈
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:

输入: "aba"
输出: True

示例 2:

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

注意:

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

思路

用双指针求字符串是否是回文字符串，当两个指针指向的字符不同了，可以知道，两个指针以外的字符已经可以构成回文字符串，只需要知道删除了左指针或者右指针指向的那个字符以后，中间的字符串是否也能构成回文字符。所以只需要再对第（i+1，j）（意味着删除左指针的那个字符）或者（i，j-1）（意味着删除右指针的那个字符）下标间的字符串进行判断是否其任意一个是不是回文字符串，是的话就可以删除一个字符得到一个回文字符串。

解答

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  const isValid = (i, j) => {
    while (i < j) {
      if (s[i++] !== s[j--]) return false;
    }
    return true;
  };
  let i = 0,
    j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return isValid(i + 1, j) || isValid(i, j - 1);
    i++;
    j--;
  }
  return true;
};