06_验证回文串(Python)

╰+攻爆jí腚メ 2023-01-13 05:58 11阅读 0赞

### 目录 ###

*  验证回文串
 *  示例 1:
 *  示例 2:
 *  解答
 *   *  1，双指针解决
     *  2，双指针的另一种写法
     *  3，使用正则匹配
     *  4，递归方式实现

# 验证回文串 #

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

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

# 示例 1: #

> 输入: “A man, a plan, a canal: Panama”  
> 输出: true

# 示例 2: #

> 输入: “race a car”  
> 输出: false

# 用isdigit函数判断是否数字
    print(str_1.isdigit())
    Ture
    
    # 用isalpha判断是否字母
    print(str_1.isalpha())    
    False
    
    # isalnum判断是否数字和字母的组合
    print(str_1.isalnum())    
    Ture
    
    注意：如果字符串中含有除了字母或者数字之外的字符，比如空格，也会返回False

# 解答 #

## 1，双指针解决 ##

这题没什么难度，最简单的就是使用双指针，一个指向前，一个指向后，遇到空格以及特殊字符要跳过，然后判断，画个图来看下

![image.png][]

class Solution:
        def isPalindrome(self, s: str) -> bool:
            i=0
            j=len(s)-1
            while(i<j):
                while(s[i].isalnum()==False and i<j):
                    i+=1
                while(s[j].isalnum()==False and i<j):
                    j-=1
                if(s[i].lower()!=s[j].lower()):
                    return False
                i+=1
                j-=1
            return True

## 2，双指针的另一种写法 ##

我们还可以在比较之前字母全部转化为小写，这里改为for循环的方式，只不过是换汤不换药，原理还都是一样的

class Solution:
        def isPalindrome(self, s: str) -> bool:
            s=s.lower()
            i=0
            j=len(s)-1
            while(i<j):
                while(s[i].isalnum()==False and i<j):
                    i+=1
                while(s[j].isalnum()==False and i<j):
                    j-=1
                if(s[i]!=s[j]):
                    return False
                i+=1
                j-=1
            return True

## 3，使用正则匹配 ##

这题还可以使用正则匹配，把特殊字符过滤掉，只留下字母和数字，然后转化为小写，再反转，最后在判断是否相等。

class Solution:
        def isPalindrome(self, s: str) -> bool:
            s = s.lower()
            s1 = re.findall(r'[a-z0-9]', s)
            s2 = "".join(s1)
            # 使用字符串切片反转
            return s2[::-1] == s2

## 4，递归方式实现 ##

如果想玩出花样，我们还可以把第一种的解题思路改为递归的方式

class Solution:
        def isPalindromeHelper(self, s, left, right):
            if left>=right:
                return True
            while(left<right and s[left].isalnum()!=True):
                left+=1
            while(left<right and s[right].isalnum()!=True):
                right-=1
            return s[left].lower()==s[right].lower() and self.isPalindromeHelper(s, left+1, right-1)
    
        def isPalindrome(self, s: str) -> bool:
            return self.isPalindromeHelper(s, 0, len(s)-1)

炫技的效率好低… 0.0

![image-20210415001622258][]

[image.png]: /images/20221022/e65edcef4d26409bb868cc29aeef1dca.png
[image-20210415001622258]: /images/20221022/94503e7bd8a4491ea089ac492b783512.png