Question

680. 验证回文串 II

English Version

题目描述

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

 

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

 

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

解法

方法一：双指针

我们用两个指针分别指向字符串的左右两端，每次判断两个指针指向的字符是否相同，如果不相同，则判断删除左指针对应的字符后字符串是否是回文字符串，或者判断删除右指针对应的字符后字符串是否是回文字符串。如果两个指针指向的字符相同，则将左右指针都往中间移动一位，直到两个指针相遇为止。

如果遍历结束，都没有遇到指针指向的字符不相同的情况，那么字符串本身就是一个回文字符串，返回 true 即可。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $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;
  }
}