字符串

回文串

真题描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解释: 你可以删除c字符。注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——对称性和双指针。这两个工具一起上，足以解决大部分的回文字符串衍生问题。

我们首先是初始化两个指针，一个指向字符串头部，另一个指向尾部：如果两个指针所指的字符恰好相等，那么这两个字符就符合了回文字符串对对称性的要求，跳过它们往下走即可。如果两个指针所指的字符串不等，比如这样：

那么就意味着不对称发生了，意味着这是一个可以“删掉试试看”的操作点。我们可以分别对左指针字符和右指针字符尝试进行“跳过”，看看区间在 [left+1, right] 或 [left, right-1] 的字符串是否回文。如果是的话，那么就意味着如果删掉被“跳过”那个字符，整个字符串都将回文：

const validPalindrome = function(s) {
  // 缓存字符串的长度
  const len = s.length

  // i、j分别为左右指针
  let i=0, j=len-1
  
  // 当左右指针均满足对称时，一起向中间前进
  while(i<j&&s[i]===s[j]) {
      i++ 
      j--
  }
  
  // 尝试判断跳过左指针元素后字符串是否回文
  if(isPalindrome(i+1,j)) {
    return true
  }
  // 尝试判断跳过右指针元素后字符串是否回文
  if(isPalindrome(i,j-1)) {
      return true
  }
  
  // 工具方法，用于判断字符串是否回文
  function isPalindrome(st, ed) {
      while(st<ed) {
          if(s[st] !== s[ed]) {
              return false
          }
          st++
          ed--
      } 
      return true
  }
  
  // 默认返回 false
  return false 
};

字符串 ​

回文串 ​

字符串

回文串