leetcode125. 验证回文串 python 简单

125. 验证回文串

难度简单

 

 

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"

输出: true

示例 2:

输入: "race a car"

输出: false

解法1:直接用双指针 硬性判断

时间复杂度：O(|s|)O(∣s∣)，其中 |s|∣s∣ 是字符串 ss 的长度。

空间复杂度：O(|s|)O(∣s∣)。由于我们需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串 \textit{sgood}sgood 与原字符串 ss 完全相同，因此需要使用 O(|s|)O(∣s∣) 的空间。

暴力破解

class Solution:

    def isPalindrome(self, s: str) -> bool:

        contener = []

        for i in s :

            if 48 <= ord(i) <= 57 or 65 <= ord(i) <= 90 or 97 <= ord(i) <= 122:

                contener.append(i.upper())

        left = 0

        right = -1

        if len(contener) ==1 :

            return True

        if len(contener)%2==1:

            while left <= len(contener)/2 - 1 :

                if contener[left] != contener[right] :

                    return False

                left += 1

                right -= 1

            return True

        while left < len(contener) / 2 :

                if contener[left] != contener[right]:

                    return False

                left += 1

                right -= 1

        return True

　　

解法二  :

原地用双指针判断

• 时间复杂度：O(|s|)O(∣s∣)，其中 |s|∣s∣ 是字符串 ss 的长度。

• 空间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