680. 验证回文字符串 Ⅱ

1. 题目描述

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

示例 1:

输入: "aba"
输出: True

示例 2:

输入: "abca"
输出: True

解释: 你可以删除c字符。

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

2. 解题思路

对于回文串，它具有对称性，我们可以使用双指针来实现：

设置两个指针i和j，分别指向第一个和最后一个字符，并进行对比，如果两者相同，就不断向中间移动，再进行对比。

如果遇到两个字符不相等，那么就与另外一个的后者或前者进行对比，有以下两种情况：

• 判断i+1 和j是否相等

• 判断i 和j-1是否相等
  如果相等，就返回true。

  3. 代码实现

  /**
  * @param {string} s
  * @return {boolean}
  */
  var validPalindrome = function(s) {
    let len =s.length
    let i = 0, j = len-1
    while (i<j&& s[i]===s[j]){
        i++
        j--
    }
    // 判断字符串是否回文
    function isPalindrome(a,b){
        while (a<b){
            if(s[a] !== s[b]){
                return false
            }
            a++
            b--
        }
        return true
    }
    if(isPalindrome(i+1,j)){
        return true
    }
    if(isPalindrome(i,j-1)){
        return true
    }
    return false
  };

  4. 提交结果