回文串Python怎么判断

Hey小伙伴们，今天来聊一个超级有趣的编程小知识点——回文串！🌟 回文串，就是正着读和反着读都一样的字符串，level”或者“radar”，这些就是典型的回文串。🔍

你有没有想过，用Python怎么来判断一个字符串是不是回文串呢？别急，我来一步步带你了解。🚀

方法一：反转字符串

最直接的方法，就是把字符串反转，然后和原字符串比较，如果两者相同，那么这个字符串就是回文串。🔄

def is_palindrome(s):
    # 去除非字母数字字符并转换为小写
    filtered_chars = [char.lower() for char in s if char.isalnum()]
    # 反转字符串
    reversed_string = ''.join(filtered_chars)[::-1]
    # 比较原字符串和反转后的字符串
    return ''.join(filtered_chars) == reversed_string

这段代码首先过滤掉所有非字母数字的字符，并将所有字符转换为小写，以确保比较时不受大小写和特殊字符的影响，它反转过滤后的字符串，并与原字符串进行比较。

方法二：双指针法

如果你不想创建一个新的反转字符串，可以使用双指针法，这种方法使用两个指针，一个从字符串的开始，一个从字符串的结束，向中间移动，比较字符是否相同。👈👉

def is_palindrome(s):
    # 同样先进行过滤和转换
    filtered_chars = [char.lower() for char in s if char.isalnum()]
    # 初始化左右指针
    left, right = 0, len(filtered_chars) - 1
    while left < right:
        # 如果左右指针指向的字符不相等，则不是回文串
        if filtered_chars[left] != filtered_chars[right]:
            return False
        # 移动指针
        left += 1
        right -= 1
    # 如果所有字符都匹配，则为回文串
    return True

这种方法的时间复杂度是O(n/2)，也就是O(n)，其中n是字符串的长度，因为我们只需要遍历一半的字符串。

方法三：递归

递归也是判断回文串的一种方法，你可以不断地去掉字符串的首尾字符，然后检查剩下的字符串是否还是回文。🌀

def is_palindrome(s):
    # 过滤和转换
    filtered_chars = [char.lower() for char in s if char.isalnum()]
    # 递归检查
    def helper(left, right):
        if left >= right:
            return True
        if filtered_chars[left] != filtered_chars[right]:
            return False
        return helper(left + 1, right - 1)
    return helper(0, len(filtered_chars) - 1)

递归方法在逻辑上很直观，但是它可能会因为深度过大而导致栈溢出，尤其是在处理非常长的字符串时。