leetcode中如何验证回文字符串

在Leetcode中，验证回文字符串的题目有多种，包括简单难度的“验证回文字符串”（Valid Palindrome）和中等难度的“验证回文字符串Ⅱ”（Valid Palindrome II）。无论是哪种题目，都涉及到如何判断一个字符串是否为回文字符串。回文字符串是指正着和倒着读都一样的字符串，比如“aba”、“level”。

方法一：双指针法

最常见的判断回文字符串的方法是双指针法。双指针分别指向字符串的最左侧和最右侧，左指针向右移动，右指针向左移动，通过比较两个指针所指的字符是否相同来判断字符串是否为回文字符串。如果相同，则继续移动指针，如果不同，则返回False。双指针可以节省空间，因为只需要遍历一遍字符串，时间复杂度为O(n)，其中n表示字符串的长度。

示例：

def isPalindrome(s: str) -> bool:
    s = ''.join(e for e in s if e.isalnum()).lower()
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

其中''.join(e for e in s if e.isalnum())可以过滤字符串中的非字母和数字字符，并返回一个新的字符串。lower()方法将字符串中的字母转换成小写字母，以便比较。

方法二：反转字符串法

除了双指针法外，还可以使用反转字符串的方法来判断回文字符串。将字符串反转后，再和原字符串进行比较，如果相同，则说明是回文字符串。该方法的时间复杂度为O(n)，空间复杂度也为O(n)。

示例：

def isPalindrome(s: str) -> bool:
    s = ''.join(e for e in s if e.isalnum()).lower()
    return s == s[::-1]

其中s[::-1]表示将字符串s反转。同样地，''.join(e for e in s if e.isalnum())可以过滤字符串中的非字母和数字字符，并返回一个新的字符串。lower()方法将字符串中的字母转换成小写字母，以便比较。

方法三：递归法

递归法是一种不太常见的判断回文字符串的方法。该方法将字符串划分为两部分，一个是 个字符，一个是最后一个字符。如果 个字符和最后一个字符相同，就递归判断去掉 个字符和最后一个字符的子串是否为回文串。如果子串是回文串，就返回True，否则返回False。

示例：

def isPalindrome(s: str) -> bool:
    def helper(left: int, right: int) -> bool:
        if left >= right:
            return True
        if s[left] != s[right]:
            return False
        return helper(left + 1, right - 1)

    s = ''.join(e for e in s if e.isalnum()).lower()
    return helper(0, len(s) - 1)

先过滤字符串中的非字母和数字字符，并将字符串转换成小写字母。helper函数用来判断是否是回文字符串，它的参数表示字符串中要判断的左右边界。如果左边界大于等于右边界，则表示已经遍历完了字符串，返回True。如果左右边界不相等，则表示不是回文字符串，返回False。否则继续递归调用helper函数，传入去掉左右边界后的子串的左右边界，继续判断。