題目

給定一個非空字符串 str，最多刪除一個字符。判斷是否能成為 回文字符串。

注意:
字符串只包含從 a-z 的小寫字母。字符串的最大長度是 50000 。

假設(shè)：

• 輸入 aba ，返回 true
• 輸入 abca ，返回 true
• 輸入 abeca ，返回 false

算法解析

• 利用回文字符串的對稱性，可以使用雙指針來優(yōu)化算法。

代碼

const validPalindrome  = (str) => {
  const arr = str.split('')
  // 初始化左右指針
  let i = 0
  let j = arr.length - 1
  // 允許被刪除
  let deleteNum = 1
  
  while(i <= j) {
    // 如果左右指針指向的字符相等
    if (arr[i] === arr[j]) {
      // 再往中間移動
      i++
      j--
    } else {
      // 如果之前已經(jīng)刪過一次了，直接返回 false
      if (deleteNum < 1) {
        return false
      }
      // 如果刪左邊指針的字符，能與當(dāng)前右邊的字符相等
      if (arr[i + 1] === arr[j]) {
        deleteNum--
        i = i + 2
        j--
      } else if (arr[i] === arr[j - 1]) {
        // 如果刪右邊指針的字符，能與當(dāng)前左邊的字符相等
        deleteNum--
        j = j - 2
        i++
      } else {
        return false
      }
    }
  }

  return true
}