• 售前

  • 售后

热门帖子
入门百科

Python实现"验证回文串"的几种方法

[复制链接]
彩云彩2017 显示全部楼层 发表于 2021-10-26 14:28:11 |阅读模式 打印 上一主题 下一主题
一、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得出结论。【字符串为有序的数据布局,可以对其举行切片操作】
代码如下:
  1. class Solution(object):
  2.   def isPalindrome(self, s):
  3.     """
  4.     :type s: str
  5.     :rtype: bool
  6.     """
  7.     # 创建一个空字符串
  8.     s_new = ''
  9.     # 遍历字符串s
  10.     for i in s:
  11.      # 判断,如果是字母或数字,将其转为小写拼接到字符串中
  12.       if i.isalnum():
  13.         s_new += i.lower()
  14.     # 切片后s_new[::-1]与s_new比较,并将结果返回
  15.     return s_new[::-1] == s_new
复制代码
方法二:双游标判定


从字符串s两头指定两个游标low,high
假如low游标指向了 非字母和数字(即空格和符号),那么low游标以后移一位;
假如high游标指向了 非字母和数字(即空格和符号),那么high游标往前移一位;
直至low和high都指向了数字或字母,此时举行比力,是否雷同。
假如比力的结果是True,则low以后移一位,high往前移一位
假如比力的结果是False,则直接返回False
重复上述判定,直至low和high重合,此时表示完成了字符串s内前后元素的逐一对比判定,返回True即可。

代码如下:
  1. class Solution(object):
  2.   def isPalindrome(self, s):
  3.     """
  4.     :type s: str
  5.     :rtype: bool
  6.     """
  7.     low = 0
  8.     high = len(s) - 1
  9.     #在字符串为空或只有一个字符时,返回True
  10.     if len(s) <= 1:
  11.       return True
  12.     # 设定low和high对比的条件
  13.     while low < high:
  14.      # 如果不是字母或数字,low往后移一位【low < high为必须条件,不然会造成索引越界】
  15.       while not s[low].isalnum() and low < high:
  16.         low += 1
  17.       # 如果不是字母或数字,high往前移一位
  18.       while not s[high].isalnum() and low < high:
  19.         high -= 1
  20.        # 判断:如果相同,继续下一次对比;如果不相同,直接返回False
  21.       if s[low].lower() == s[high].lower():
  22.         low += 1
  23.         high -= 1
  24.       else:
  25.         return False
  26.     # low和high重合,即退出循环,表示前后都是一一对应的,返回True
  27.    return True
复制代码
四、总结


以上就是本日的解题,此题目从字符串切片的解题方式来看,观察了我们对字符串常见功能的掌握情况,而双游标的角度来看,紧张观察了我们对游标这一工具的机动运用,信赖各人在学习根本算法——快速排序时,会再次碰到双游标,而快速排序可以说是相称于在本文核心代码的根本上再嵌套一层外层循环。

增补:其他方法

1:起首将字符串大写字母转为小写字母,然后去掉字符串中非字母和数字的别的字符,翻转对比输出结果(时间复杂度O(n))
  1. def isPalindrome(self, s):
  2.     """
  3.     :type s: str
  4.     :rtype: bool
  5.     """
  6.     s = s.lower()
  7.     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']
  8.     newStr = ""
  9.     for i in s:
  10.       if i in alphanumeric:
  11.         newStr += i
  12.     return newStr==newStr[::-1]
复制代码
2:str.lower()+str.isalnum()(时间复杂度O(n))
  1. def isPalindrome(self, s):
  2.     """
  3.     :type s: str
  4.     :rtype: bool
  5.     """
  6.     s = s.lower()
  7.     newStr = ""
  8.     for i in s:
  9.       if i.isalnum():
  10.         newStr += i
  11.     return newStr==newStr[::-1]
复制代码
3:引入re模块(正则表达式),re.sub()
  1. def isPalindrome(self, s):
  2.     """
  3.     :type s: str
  4.     :rtype: bool
  5.     """
  6.     s = s.lower()
  7.     import re
  8.     s = re.sub('[^a-z0-9]', "", s)
  9.     return s==s[::-1]
复制代码
到此这篇关于Python实现"验证回文串"的几种方法的文章就先容到这了,更多相关Python 验证回文串内容请搜索草根技能分享从前的文章或继承欣赏下面的相关文章盼望各人以后多多支持草根技能分享!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作