680.验证回文串II

链接：680.验证回文串II
难度：Easy
标签：贪心、双指针、字符串
简介：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

题解 1 - javascript

• 编辑时间：2020-02-23
• 执行用时：116ms
• 内存消耗：42.8MB
• 编程语言：javascript
• 解法介绍：从左右依次递进，遇到不匹配判断进一位是否相同，题目有个问题，发现输入 ac 返回 true。

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  let isDel = false;
  function comp(start, endStart) {
    if (endStart <= start) return true;
    while (start < endStart) {
      if (s[start] !== s[endStart]) {
        if (isDel) return false;
        isDel = true;
        return comp(start + 1, endStart) || comp(start, endStart - 1);
      }
      start++;
      endStart--;
    }
    return true;
  }
  return comp(0, s.length - 1);
};

题解 2 - cpp

• 编辑时间：2022-02-18
• 执行用时：48ms
• 内存消耗：19MB
• 编程语言：cpp
• 解法介绍：双指针遍历。

class Solution {
   public:
    bool check(string &s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return 0;
            l++;
            r--;
        }
        return 1;
    }
    bool validPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        for (int l = 0, r = s.size() - 1; l < r; l++, r--) {
            if (s[l] == s[r])
                continue;
            else
                return check(s, l, r - 1) || check(s, l + 1, r);
        }
        return 1;
    }
};