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

一、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

四、总结

以上就是今天的解题,此题目从字符串切片的解题方式来看,考察了我们对字符串常见功能的掌握情况,而双游标的角度来看,主要考察了我们对游标这一工具的灵活运用,相信大家在学习基础算法——快速排序时,会再次遇到双游标,而快速排序可以说是相当于在本文核心代码的基础上再嵌套一层外层循环。

补充:其他方法

1:首先将字符串大写字母转为小写字母,然后去掉字符串中非字母和数字的其它字符,翻转对比输出结果(时间复杂度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]

2: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]

3:引入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实现"验证回文串"的几种方法的文章就介绍到这了,更多相关Python 验证回文串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-03-28

python最长回文串算法

给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

Python3最长回文子串算法示例

本文实例讲述了Python3最长回文子串算法.分享给大家供大家参考,具体如下: 1. 暴力法 思路:对每一个子串判断是否回文 class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) == 1: return s re = s[0] for i in range(0,len(s)-1): for j in range(i+1

js如何找出字符串中的最长回文串

本文实例为大家分享了js找出字符串中的最长回文串的具体代码,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <title>回文</title> <link rel=&q

python实现对求解最长回文子串的动态规划算法

基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

python实现求最长回文子串长度

给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

Python实现常见的回文字符串算法

回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

python实现寻找最长回文子序列的方法

本文实例为大家分享了python实现寻找最长回文子序列,这一类的问题可以使用动态规划的方法去做,我之前应该有几篇博文都是关于回文序列的求解的,正好有可以复用的代码就懒得再用别的方法写了,直接套用,思想还是滑窗切片,很简单就是运算会多点,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:寻找最长回文子序列 ''' def slice_window(one_str,w=1): ''''' 滑窗函数 ''' r

Python实现判断一个整数是否为回文数算法示例

本文实例讲述了Python实现判断一个整数是否为回文数算法.分享给大家供大家参考,具体如下: 第一个思路是先将整数转换为字符串,再将字符串翻转并与原字符串做比较 def isPalindrome(self, x): """ :type x: int :rtype: bool """ #思路:先将整数转换为字符串,再将字符串翻转并与原字符串做比较 x = str(x) return x == x[::-1] 代码简洁 第二个思路,尝试着不用字符串,

Java实现查找当前字符串最大回文串代码分享

先看代码 public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1.输出回文串 public static void MaxHuiWen(String s){ //存储字符串的长度 int length = s.length(); //存储最长的回文串 String M

Python3实现的判断回文链表算法示例

本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置