125.验证回文串
题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
解释：”amanaplanacanalpanama” 是回文串
思路
1.判断第i(0 < i < len(new_s)//2)个字符与倒数第i个字符是否相等来确定字符串是否回文，其中new_s是去除了除数字字母外字符的字符串
2.判断反转字符串是否与原字符串相同
3.双指针（去除除数字字母外的其他字符）
初始时，左右指针分别指向字符串的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明是回文串。
4.双指针（直接在原字符串上进行判断）
与3.相同
代码
class Solution:
def isPalindrome(self, s: str) -> bool:
import re
new_s = re.sub(r'\W|_', '', s).lower()
len_new_s = len(new_s)
i = 0
while i < len_new_s // 2:
if new_s[i] == new_s[len_new_s-i-1]:
i += 1
else:
break
if i == len_new_s // 2:
return True
else:
return False
def isPalindrome1(self, s: str) -> bool:
"""
筛选+判断（判断反转字符串是否与原字符串相同）
:param s:
:return:
"""
new_s = "".join(ch.lower() for ch in s if ch.isalnum())
return new_s == new_s[::-1]
def isPalindrome2(self, s: str) -> bool:
"""
双指针
"""
new_s = "".join(ch.lower() for ch in s if ch.isalnum())
left, right = 0, len(new_s) - 1
while left < right:
if new_s[left] != new_s[right]:
return False
left, right = left + 1, right - 1
return True
def isPalindrome3(self, s: str) -> bool:
"""在原字符串上直接判断"""
n = len(s)
left, right = 0, n - 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 left < right:
if s[left].lower() != s[right].lower():
return False
left, right = left + 1, right - 1
return True
if __name__ == "__main__":
slt = Solution()
string = "abcb"
res = slt.isPalindrome(string)
print(res)