验证回文串【双指针、字符串】

力扣https://leetcode.cn/problems/valid-palindrome/description/?envTypestudy-plan-v2envIdtop-interview-150如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。字母和数字都属于字母数字字符。给你一个字符串 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 是一个空字符串 。由于空字符串正着反着读都一样所以是回文串。方法一筛选 判断class Solution: def isPalindrome(self, s: str) - bool: sgood .join(ch.lower() for ch in s if ch.isalnum()) return sgood sgood[::-1]第二种是使用双指针。初始时左右指针分别指向 sgood 的两侧随后我们不断地将这两个指针相向移动每次移动一步并判断这两个指针指向的字符是否相同。当这两个指针相遇时就说明 sgood 是回文串。class Solution: def isPalindrome(self, s: str) - bool: sgood .join(ch.lower() for ch in s if ch.isalnum()) n len(sgood) left, right 0, n - 1 while left right: if sgood[left] ! sgood[right]: return False left, right left 1, right - 1 return Truefunc isPalindrome(s string) bool { var sgood string for i : 0; i len(s); i { if isalnum(s[i]) { sgood string(s[i]) } } sgood strings.ToLower(sgood) left, right : 0, len(sgood)-1 for left right { if sgood[left] ! sgood[right] { return false } left right-- } return true } func isalnum(ch byte) bool { return (ch A ch Z) || (ch a ch z) || (ch 0 ch 9) }方法二在原字符串上直接判断class Solution: def isPalindrome(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 Truefunc isPalindrome(s string) bool { s strings.ToLower(s) left, right : 0, len(s) - 1 for left right { for left right !isalnum(s[left]) { left } for left right !isalnum(s[right]) { right-- } if left right { if s[left] ! s[right] { return false } left right-- } } return true } func isalnum(ch byte) bool { return (ch A ch Z) || (ch a ch z) || (ch 0 ch 9) }