Python实现验证回文串的方法有哪些

这篇文章主要介绍了Python实现"验证回文串"的方法有哪些，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

python可以做什么

Python是一种编程语言，内置了许多有效的工具，Python几乎无所不能，该语言通俗易懂、容易入门、功能强大，在许多领域中都有广泛的应用，例如最热门的大数据分析，人工智能，Web开发等。

一、LeetCode——125.验证回文串

1.问题描述

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

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

2.示例

示例 1:
输入: “A man, a plan, a canal: Panama”
输出: True

示例 1:
输入: “race a car”
输出: False

示例 3:
输入: “!!!”
输出: True

二、解题分析

在排除空格及特殊字符的前提下，且不考虑字母大小写，字符串前后元素一一相同.
在字符串为空或只有一个字符时，应该返回True
字符串的元素全部是符号是应该返回True

三、解题思路及代码实现

方法一：字符串切片

创建一个空字符串s_new，通过遍历字符串s，将字符串s中的字母和数字，拼接到s_new中，
通过比较s_new[::-1] 和s_new得出结论。【字符串为有序的数据结构，可以对其进行切片操作】
代码如下：

class Solution(object):  def isPalindrome(self, s):    """    :type s: str    :rtype: bool    """    # 创建一个空字符串    s_new = ''    # 遍历字符串s    for i in s:     # 判断，如果是字母或数字，将其转为小写拼接到字符串中      if i.isalnum():        s_new += i.lower()    # 切片后s_new[::-1]与s_new比较，并将结果返回    return s_new[::-1] == s_new

方法二：双游标判断

从字符串s两端指定两个游标low，high
如果low游标指向了 非字母和数字（即空格和符号）,那么low游标往后移一位；
如果high游标指向了 非字母和数字（即空格和符号）,那么high游标往前移一位；
直至low和high都指向了数字或字母，此时进行比较，是否相同。
如果比较的结果是True，则low往后移一位，high往前移一位
如果比较的结果是False，则直接返回False
重复上述判断，直至low和high重合，此时表示完成了字符串s内前后元素的一一对比判断，返回True即可。

代码如下：

class Solution(object):  def isPalindrome(self, s):    """    :type s: str    :rtype: bool    """    low = 0    high = len(s) - 1    #在字符串为空或只有一个字符时，返回True    if len(s) <= 1:      return True    # 设定low和high对比的条件    while low < high:     # 如果不是字母或数字，low往后移一位【low < high为必须条件，不然会造成索引越界】      while not s[low].isalnum() and low < high:        low += 1      # 如果不是字母或数字，high往前移一位      while not s[high].isalnum() and low < high:        high -= 1       # 判断：如果相同，继续下一次对比；如果不相同，直接返回False      if s[low].lower() == s[high].lower():        low += 1        high -= 1      else:        return False    # low和high重合，即退出循环，表示前后都是一一对应的，返回True   return True

四、总结

补充：其他方法

首先将字符串大写字母转为小写字母，然后去掉字符串中非字母和数字的其它字符，翻转对比输出结果（时间复杂度O(n)）

def isPalindrome(self, s):    """    :type s: str    :rtype: bool    """    s = s.lower()    alphanumeric = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6','7','8','9']    newStr = ""    for i in s:      if i in alphanumeric:        newStr += i    return newStr==newStr[::-1]

str.lower()+str.isalnum()（时间复杂度O(n)）

def isPalindrome(self, s):    """    :type s: str    :rtype: bool    """    s = s.lower()    newStr = ""    for i in s:      if i.isalnum():        newStr += i    return newStr==newStr[::-1]

引入re模块（正则表达式），re.sub()

def isPalindrome(self, s):    """    :type s: str    :rtype: bool    """    s = s.lower()    import re    s = re.sub('[^a-z0-9]', "", s)    return s==s[::-1]

感谢你能够认真阅读完这篇文章，希望小编分享的“Python实现"验证回文串"的方法有哪些”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网行业资讯频道，更多相关知识等着你来学习!