验证回文字符串

这里做几道与回文数相关的简单题

回文数（力扣9）

思路1：转字符串之后判断

1
2
3
class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

思路2：通过数字判断(这里要注意x发生变化了，最后判断时需要与原始的x进行比较)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isPalindrome(self, x: int) -> bool:
        before = x
        if x < 0:
            return False
        res = 0
        while x>0:
            res = res*10 + x%10
            x = x//10
        return res == before

回文排列（力扣266）

思路：字典判断个数即可,小于等于1个则返回True

1
2
3
4
5
6
7
8
9
from collections import Counter
class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        temp = Counter(s)
        count = 0
        for i in temp:
            if temp[i]%2 == 1:
                count += 1
        return count <= 1

验证回文串（力扣125）

思路：和上题相同

1
2
3
4
class Solution:
    def isPalindrome(self, s: str) -> bool:
        result = "".join(i.lower() for i in s if i.isalnum())
        return result == result[::-1]

这里学习到可以直接使用isalnum()。注意的是空格不算alpha。示例如下：

1
2
3
4
5
6
7
8
s1, s2, s3 = "a", "1232", "adfds123    12"
print(s1.isdigit(), s2.isdigit(), s3.isdigit())
print(s.isalpha(), s2.isalpha(), s3.isalpha())
print(s.isalnum(), s2.isalnum(), s3.isalnum())

False True False
True False False
True True False

最长回文串（力扣653）

思路：最终结果是由所有偶数与奇数减一组成。需要注意，如果没有奇数时，最终结果不加一

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import Counter
class Solution:
    def longestPalindrome(self, s: str) -> int:
        temp = Counter(s)
        result = 0
        flag = False
        for i in temp:
            if temp[i]%2 == 0:
                result += temp[i]
            else:
                flag = True
                result += temp[i] - 1
        return result + 1 if flag else result

验证回文字符串II（力扣680）

首先想到了暴力法：超出时间限制

1
2
3
4
5
6
7
8
9
class Solution:
    def isP(self,s):
        return s == s[::-1]
    def validPalindrome(self, s: str) -> bool:
        if self.isP(s):return True
        for index in range(len(s)):
            if self.isP(s[:index] + s[index+1:]):
                return True
        return False

然后改进，使用双指针逼近（这里left<=right或者left<right都行，因为最终right=left的位置一定是True的）。需要注意的是要想到删除左和右的两种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s)-1
        count = 0
        while left<=right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                remove_left = s[left+1:right+1]
                remove_right = s[left:right]
                return True if remove_left[::-1] == remove_left or remove_right[::-1] == remove_right else False
        return True