Palindrome String
如果一个字符串从左向右读和从右向左读都一样，它就是回文，例如 level。编写一个函数，接收由小写英文字母组成的字符串 s，如果 s 是回文，则返回 true，否则返回 false。
函数
- sstring
- 要检查的小写字符串
- 返回值boolean
- 当 s 从两个方向读取时都相同时
约束条件
1 ≤ s.length ≤ 5 × 104s只包含小写英文字母（从a到z）。
示例
- 输入
- s = "racecar"
- 输出
- true
- 解释
- 从外向内比较：
r和r，a和a，c和c。中间的e没有配对，也不需要配对，所以答案是true。
- 输入
- s = "abba"
- 输出
- true
- 解释
- 长度为偶数时，每个字母都有一个配对：两个
a配成一对，两个b配成一对，所以答案是true。
- 输入
- s = "coddy"
- 输出
- false
- 解释
- 第一个字母
c和最后一个字母y已经不同了，所以coddy不是回文，答案是false。
进阶
你会如何修改这两个指针，让它们跳过空格和标点并忽略大小写，从而使 Was it a car or a cat I saw 被视为回文？
提示
逐个打开提示，每个都会多透露一点。
如果
s是回文，它的第一个字符必须与哪个字符相同？索引
i处的字符必须等于索引n-1-i处的字符。每一对这样的字符只需检查一次，因此检查一半的索引就够了。在开头和结尾各放置一个索引。比较这两个字符，如果不匹配，就返回
false，然后将两个索引都向内移动一步，直到它们相遇。
题解
回文与它反转后的结果相同，所以你可以构造反转结果并进行比较。你不需要复制字符串：第一个字符必须与最后一个字符相同，第二个字符必须与倒数第二个字符相同，以此类推。用两个索引从两端向中间移动，就能原地检查这些字符对，并在发现第一个不匹配时停止。
将字符串与其反转后的字符串进行比较
思路
反转 s 并进行比较：racecar 反转后是 racecar，而 coddy 反转后是 yddoc。当字符串与其反转后的结果相等时，它正反读起来才完全相同。
时间复杂度是 O(n)，但反转后的副本会额外占用 O(n) 空间，当 n = 5 × 10^4 时，就是 50,000 个字符。此外，这种做法总是会处理完整个字符串：只看 coddy 的首字母和末字母就能得出结果，但还是会先反转全部五个字符。
算法
- 构造
s的反转结果，可以使用该语言的反转函数，也可以用循环从最后一个字符遍历到第一个字符。 - 将反转结果与
s进行比较。 - 如果两者相等，则返回
true；否则返回false。
def isPalindrome(s):
return s == s[::-1]从两端出发的双指针
思路
反转会将索引 i 移到索引 n-1-i，因此当每个 i 都满足 s[i] 等于 s[n-1-i] 时，s 才恰好等于它的反转结果。这个条件中的每一对都会出现两次，因此只检查左半部分就够了。在 racecar 中，这些配对是 (0, 6)、(1, 5) 和 (2, 4)；索引 3 处中间的 e 不需要配对。
第一对不相同的字符就能证明答案是 false，因此只需比较一次就能判断 coddy。最多会进行 n / 2 次比较，时间复杂度为 O(n)，两个索引占用 O(1) 空间。R 首先会将字符串读取为字符代码向量，这一步的时间复杂度为 O(n)。
算法
- 将
left = 0和right = n-1。 - 当
left < right时，比较s[left]和s[right]。 - 如果它们不同，则返回
false。 - 否则，将
left加 1，将right减 1，然后重复。 - 当两个指针相遇或交错时，每一对都已匹配：返回
true。
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
易错点和边界情况
- 只要有一对匹配，就立即返回
true。abca的外层字符对匹配，但内层字符对不匹配，所以要等循环结束后才能返回true。 - 将
right的初始值设为n，而不是n-1，这样会读到末尾之后的位置（在 C 中，就是终止符'\0'之后的位置）。在 Lua 和 R 中，索引从 1 开始，到n结束，所以right在这两种语言中确实从n开始。 - 在 C 中用
==比较字符串。reversed == s比较的是两个指针，对于副本结果为假；应该使用strcmp。 - 用
result = result + ch构建反转后的字符串。每一步都会复制目前的字符串：对于 50,000 个字母，大约会复制1.25 × 10^9个字符。 - 用整数索引访问 Swift 字符串：这无法编译。遍历
s.utf8，或将字符复制到数组中。
常见问题4
如何检查一个字符串是否是回文？
将第一个字符与最后一个字符比较，将第二个字符与倒数第二个字符比较，依此类推，逐步向中间靠拢。如果有任何一对字符不同，这个字符串就不是回文。两个索引分别从两端开始向内移动，只需遍历一次即可完成比较。
你能在不使用额外内存的情况下检查一个回文吗？
是的。双指针检查会直接读取字符，并存储两个索引，因此只使用 O(1) 的额外空间。将 s 与它的反转结果进行比较，写起来更简短，但会创建一个包含 n 个字符的第二个字符串。
检查一个回文字符串的时间复杂度是多少？
对于长度为 n 的字符串，时间复杂度为 O(n)。双指针检查最多进行 n / 2 次比较，并在首次不匹配时停止，因此 coddy 只需比较一次。
单个字符是回文吗？
是的，两个方向读起来都一样。在双指针循环中，left 和 right 都从索引 0 开始，循环不会运行，函数会返回 true。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPalindrome(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "racecar"
预期输出
true