<div>
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
<pre>Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. </pre>
Example 2:
<pre>Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. </pre>
Example 3:
<pre>Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. </pre>
Constraints:
1 <= s.length <= 2 * 10<sup>5</sup>sconsists only of printable ASCII characters.
</div>
题目大意：
求含非字母数字的字符串是否回文，字符串含空格，冒号等. Easy题
双指针解题思路(推荐)：
回文首先考虑用相向双指针
解题步骤：
N/A
注意事项：
- 比较时，要转换成小写
- 外循环left < right条件要复制到内循环中
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
reverse法算法II解题思路：
reverse字符串比较
注意事项：
- 比较时，要转换成小写
Python代码：
1
2
3
4
5
6def isPalindrome2(self, s: str) -> bool:
res = ''
for char in s:
if char.isalpha() or char.isdigit():
res += char.lower()
return True if res == res[::-1] else False
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
