Valid Palindrome
给你一个字符串 s。只保留其中的字母和数字，将大写字母和小写字母视为相同的字母，然后判断剩下的内容从左向右读和从右向左读是否相同。如果相同，返回 true，否则返回 false。
其他所有字符，例如 .、!、?、:、;、- 或 _，都会被忽略。如果 s 中没有任何字母或数字，剩下的内容就是空文本，而空文本也算回文。
函数
- sstring
- 要检查的文本，包括标点
- 返回值boolean
- 如果忽略大小写，s 中的字母和数字正着读和反着读都相同，则结果为真
约束条件
1 ≤ s.length ≤ 5 × 104s包含英文字母、数字和标点符号. ! ? : ; - _，且不含空格。
示例
- 输入
- s = "Was_it_a_car_or_a_cat_I_saw?"
- 输出
- true
- 解释
- 去掉下划线和问号，再把大写字母改成小写：你会得到
wasitacaroracatisaw，它正着读和倒着读都一样。
- 输入
- s = "race-a-car"
- 输出
- false
- 解释
- 去掉连字符后，文本是
raceacar。中间的e与a互为镜像伙伴，所以答案是false。
- 输入
- s = "Step-on-no-pets!"
- 输出
- true
- 解释
- 保留的文本是
steponnopets。大写字母S与末尾的s匹配，因为不区分大小写，连字符和!都不起作用。
进阶
你能否在不创建 s 的清理副本的情况下，仅使用 O(1) 额外内存来判断？
提示
逐个打开提示，每个都会多透露一点。
先暂时忽略标点。回文检查实际会比较
s中的哪些字符？它们是如何配对的？第一个字母或数字会与最后一个进行比较，第二个会与倒数第二个进行比较，依此类推，比较时不区分大小写。标点符号不会参与比较，所以只会妨碍你找到下一对字符。
从开头向前移动一个索引，从结尾向后移动一个索引。让任一索引越过所有非字母或数字的字符；当两个字符都保留时，比较它们，并在两个索引相遇时停止。
题解
检查方法和平常一样：保留的第一个字符必须与最后一个字符相同，第二个字符必须与倒数第二个字符相同，以此类推。问题在于，由于标点符号分布不均匀，保留的字符不会位于 s 中互为镜像的索引处。你可以先移除标点符号，也可以让两个指针向内移动，同时跳过标点符号。
清理字符串，然后将它与反转后的字符串进行比较
思路
遍历 s，将每个字母或数字转换为小写，并跳过其他内容：Step-on-no-pets! 会变成 steponnopets。清理时只移除题目要求忽略的内容，因此只需判断这段文本是否等于它的反转结果。没有字母或数字的字符串会被清理为空文本，而空文本等于它的反转结果，无需特殊处理。
时间复杂度为 O(n)，副本及其反转结果需要 O(n) 的额外内存。
算法
- 创建一个空字符串
cleaned。 - 遍历
s中的每个字符，如果它是字母或数字，就将其转换为小写并追加。 - 反转
cleaned。 - 返回
cleaned是否等于其反转结果。
def isPalindrome(s):
cleaned = [ch.lower() for ch in s if ch.isalnum()]
return cleaned == cleaned[::-1]跳过标点的双指针
思路
清理后的副本只用于比较对称位置的字符，你可以直接比较 s。让两个指针分别越过标点符号，然后比较小写形式的两个字符。指针总会停在两端下一个保留的字符上，因此它们依次访问（第一个保留字符，最后一个保留字符）、（第二个保留字符，倒数第二个保留字符）等字符对：这正是反向比较所检查的字符对。
每一步至少会移动一个指针，因此循环最多运行 n 次，而且只存储两个索引。它也会在遇到第一个不匹配时停止：比较 Abc-dcbX 中的 A 和 X 后，结果就是 false。
算法
- 将
left = 0和right = n-1设为初始值。 - 当
left < right时：如果s[left]不是字母或数字，就增加left并继续。 - 否则，如果
s[right]不是字母或数字，就减小right并继续。 - 否则，将两个字符转换为小写后进行比较。如果它们不同，返回
false；如果相同，就将两个指针同时向内移动。 - 当两个指针相遇时，返回
true。
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True
易错点和边界情况
- 在原始字符串中比较
s[i]和s[n-1-i]。去掉连字符后，a-ba是回文，但原始字符串中索引 1 处的-，镜像位置对应的是索引 2 处的b。 - 只有一侧指针指向标点符号时，却同时移动两个指针。应一次只跳过一侧，否则两侧的位置会错开。
- 在内部循环中跳过标点符号，却不检查
left < right。对于?!-_，循环会越过字符串末尾。 - 把数字当作无关字符。
0P是false：0会保留，而且它不是字母p。 - 在 PHP 和 R 中，像
12321这样的数字字符串可能会以数字的形式传入。请先将其转换为字符串。
常见问题3
验证回文字符串的时间复杂度是多少？
这两种方法的运行时间都是 O(n)，因为每个字符都会被查看常数次。先清理字符串会为副本额外使用 O(n) 内存。双指针版本额外使用 O(1) 内存，因为它只保存两个索引。
空字符串是回文吗？
是的。空文本正反读起来都一样，因此像 ?!-_ 这样所有字符都会被忽略的字符串会返回 true。两种方法都无需额外代码就能实现这一点：清理后的文本等于它反转后的空文本，而且两个指针始终找不到不相同的一对字符。
为什么使用双指针，而不是反转字符串？
反转需要一份清理后的副本和一份反转后的副本，这会额外占用 O(n) 内存。两个指针在原地比较相同的元素对，并在遇到第一个不匹配的元素时停止，通常几步后就会停止。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPalindrome(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "Was_it_a_car_or_a_cat_I_saw?"
预期输出
true