4. 125.验证回文串

题目描述：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

我写的版本：

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newlist = []
        Flag = True
        for i in s.lower():
            if i.isalnum():
                newlist.append(i)
        for j in range(len(newlist)//2):
            if newlist[j] != newlist[len(newlist)- 1 -j]:
                Flag = False
                break
        return Flag

官方解答1：时间复杂度O(n)，空间复杂度O(n)。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        sgood = "".join(ch.lower() for ch in s if ch.isalnum())
        return sgood == sgood[::-1]

官方解答2：时间复杂度O(n)，空间复杂度O(n)，最坏情况下新字符串与原字符串相同

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 True

官方解答3：时间复杂度O(n)，空间复杂度：O(1)。在原字符串上判断。遇到非字母数字向前移动，遇到字母数字比较小写后是否相等，若相等前进。

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 True