Leetcode

Valid Palindrome II

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  bool validPalindrome(string s) {
    for (int l = 0, r = s.length() - 1; l < r; ++l, --r)
      if (s[l] != s[r])
        return validPalindrome(s, l + 1, r) ||
               validPalindrome(s, l, r - 1);
    return true;
  }

 private:
  bool validPalindrome(const string& s, int l, int r) {
    while (l < r)
      if (s[l++] != s[r--])
        return false;
    return true;
  }
};

JAVA

class Solution {
  public boolean validPalindrome(String s) {
    for (int l = 0, r = s.length() - 1; l < r; ++l, --r)
      if (s.charAt(l) != s.charAt(r))
        return validPalindrome(s, l + 1, r) || validPalindrome(s, l, r - 1);
    return true;
  }

  private boolean validPalindrome(final String s, int l, int r) {
    while (l < r)
      if (s.charAt(l++) != s.charAt(r--))
        return false;
    return true;
  }
}

Python

class Solution:
  def validPalindrome(self, s: str) -> bool:
    def validPalindrome(l: int, r: int) -> bool:
      return all(s[i] == s[r - i + l] for i in range(l, (l + r) // 2 + 1))

    n = len(s)

    for i in range(n // 2):
      if s[i] != s[~i]:
        return validPalindrome(i + 1, n - 1 - i) or validPalindrome(i, n - 2 - i)

    return True