680.md

680. Valid Palindrome II

Leetcode link

解题思路

本题要求我们检测回文字符串，并且可以最多丢弃任一字符。

检测回文的其中一个方法就是用双指针往中间遍历，由于我们可以丢弃任一字符，我们需要考虑遇到不匹配的情况下要删除哪一边的字符。

解决方法是两边都试一下，只要有一边成功了，就表示这个字符是符合要求的。

C++

class Solution {
 public:
  bool isValid(string s, int left, int right) {
    while (left < right) {
      if (s[left] != s[right])
        return false;
      else {
        left++;
        right--;
      }
    }
    return true;
  }

  bool validPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
      if (s[left] != s[right]) {
        return isValid(s, left + 1, right) || isValid(s, left, right - 1);
      } else {
        left++;
        right--;
      }
    }
    return true;
  }
};

Javascript

var validPalindrome = function(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
      if (s[left] != s[right]) {
        return isValid(s, left + 1, right) || isValid(s, left, right - 1);
      } else {
        left++;
        right--;
      }
    }
    return true;
};

var isValid = function(s, left, right) {
    while (left < right) {
      if (s[left] != s[right])
        return false;
      else {
        left++;
        right--;
      }
    }
    return true;
}