难度: Easy
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。
示例 3：
输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
提示：
1 <= s.length <= 2 * 105s 仅由可打印的 ASCII 字符组成运行时间: 20 ms
内存: 17.6 MB
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
s = "".join(filter(str.isalnum, s))
n = len(s)
k = n // 2
for i in range(k):
if s[i] == s[n - 1 - i]:
continue
else:
return False
return True
此题解通过首先将输入字符串转换为小写，然后利用filter函数结合str.isalnum方法移除所有非字母数字字符，得到纯净的字符串s。随后，通过比较字符串的前半部分和后半部分（反向）的字符是否一致来判断字符串是否为回文。如果在比较过程中发现不匹配的字符，则立即返回false。如果所有对应位置的字符都相同，最终返回true。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower() # 将所有字符转为小写
s = "".join(filter(str.isalnum, s)) # 移除所有非字母数字字符
n = len(s) # 获取处理后字符串的长度
k = n // 2 # 只需比较字符串的一半长度
for i in range(k): # 检查是否为回文
if s[i] == s[n - 1 - i]: # 比较字符是否相等
continue # 如果相等，继续比较下一个字符
else:
return False # 如不相等，立即返回false
return True # 如果所有字符都相等，则返回true
在处理回文字符串时，重要的一步是确保比较的一致性和无歧义性。将字符串先转化为小写是为了消除大写和小写字符之间的差异，确保回文比较时字符的统一性。此操作后再过滤非字母数字字符，是因为大小写转换仅适用于字母，而非字母数字字符在回文验证中无意义，应被排除。如果先过滤再转换小写，可能会有不必要的性能开销，因为非字母数字字符无需转换。因此，这样的顺序既逻辑合理又效率较高。
对于空字符串或只包含非字母数字字符的字符串，在过滤非字母数字字符后，结果将是一个空字符串。在此算法中，空字符串被认为是回文，因为回文的定义是正向和反向读都一样，空字符串符合这一标准。因此，算法将返回true。
算法实际上只使用了一个单层循环来从两端向中心比较字符直到中间的位置。这是一种高效的方法，因为它最多只比较字符串的一半字符。尽管如此，还可以通过一些技术进一步提高效率，例如使用双指针技术从两端向中心移动，这可以稍微减少代码复杂性并可能提高一些实际运行效率。然而，基本的时间复杂度仍然是 O(n)。
使用`filter`和`str.isalnum`的原因主要是代码的可读性和简洁性。`str.isalnum`直接检测字符是否是字母或数字，非常直观且易于理解。虽然正则表达式同样可以实现字符过滤的功能，但它通常更复杂，对于初学者可能不够友好。此外，对于这种简单的字符检测，`str.isalnum`在功能上完全足够，且执行效率通常与正则表达式相当。