Question

680. Valid Palindrome II

中文文档

Description

Given a string s, return true _if the _s_ can be palindrome after deleting at most one character from it_.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solutions

Solution 1: Two Pointers

We use two pointers to point to the left and right ends of the string, respectively. Each time, we check whether the characters pointed to by the two pointers are the same. If they are not the same, we check whether the string is a palindrome after deleting the character corresponding to the left pointer, or we check whether the string is a palindrome after deleting the character corresponding to the right pointer. If the characters pointed to by the two pointers are the same, we move both pointers towards the middle by one position, until the two pointers meet.

If we have not encountered a situation where the characters pointed to by the pointers are different by the end of the traversal, then the string itself is a palindrome, and we return true.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

class Solution:
  def validPalindrome(self, s: str) -> bool:
    def check(i, j):
      while i < j:
        if s[i] != s[j]:
          return False
        i, j = i + 1, j - 1
      return True

    i, j = 0, len(s) - 1
    while i < j:
      if s[i] != s[j]:
        return check(i, j - 1) or check(i + 1, j)
      i, j = i + 1, j - 1
    return True

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

  private boolean check(String s, int i, int j) {
    for (; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool validPalindrome(string s) {
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
      if (s[i] != s[j]) {
        return check(s, i + 1, j) || check(s, i, j - 1);
      }
    }
    return 1;
  }

  bool check(string s, int i, int j) {
    for (; i < j; ++i, --j) {
      if (s[i] != s[j]) {
        return false;
      }
    }
    return true;
  }
};

func validPalindrome(s string) bool {
  check := func(i, j int) bool {
    for ; i < j; i, j = i+1, j-1 {
      if s[i] != s[j] {
        return false
      }
    }
    return true
  }
  for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
    if s[i] != s[j] {
      return check(i+1, j) || check(i, j-1)
    }
  }
  return true
}

function validPalindrome(s: string): boolean {
  for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
    if (s.charAt(i) != s.charAt(j)) {
      return isPalinddrome(s.slice(i, j)) || isPalinddrome(s.slice(i + 1, j + 1));
    }
  }
  return true;
}

function isPalinddrome(s: string): boolean {
  for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
    if (s.charAt(i) != s.charAt(j)) {
      return false;
    }
  }
  return true;
}

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function (s) {
  let check = function (i, j) {
    for (; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  };
  for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
    if (s.charAt(i) != s.charAt(j)) {
      return check(i + 1, j) || check(i, j - 1);
    }
  }
  return true;
};

public class Solution {
  public bool ValidPalindrome(string s) {
    int i = 0, j = s.Length - 1;
    while (i < j && s[i] == s[j]) {
      i++;
      j--;
    }
    if (i >= j) {
      return true;
    }
    return check(s, i + 1, j) || check(s, i, j - 1);
  }

  private bool check(string s, int i, int j) {
    while (i < j) {
      if (s[i] != s[j]) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  }
}