当前位置:首页 > 编程技术 > 正文内容

【说站】Python找回文子串的方法

yc8882年前 (2022-11-17)编程技术222

Python找回文子串的方法

1、双指针两边扩展

遍历指针为i, j=i+1, i左移,j右移。判断是否相等将长度,下标赋给临时变量,最后切片返回。唯一的大坑。回文字符串长度可以是奇数也可以是偶数。奇数的时候,内层循环从i-1开始。边界条件也需要处理好。

class Solution(object):
        
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        maxL, maxR, max = 0, 0, 0
        for i in range(n):
            # 长度为偶数的回文字符串
            start = i
            end = i + 1
            while start >= 0 and end < n:
                if s[start] == s[end]:
                    if end - start + 1 > max:
                        max = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
    
            # 长度为奇数的回文子串
            start = i - 1
            end = i + 1
            while start >= 0 and end < n:
                if s[start] == s[end]:
                    if end - start + 1 > max:
                        max = end - start + 1
                        maxL = start
                        maxR = end
                    start -= 1
                    end += 1
                else:
                    break
        return s[maxL:maxR+1]

2、Manacher算法

由于在输入预处理的步骤中,将所有的回文子字符已经转为奇数长度。所以在下面的操作中,只需要将输入的每一个字符,都当做一个回文子字符的中心位即可。不需要考虑偶数长度的回文子字符。

'''
@author: Yizhou Zhao
'''
# 设置 radius[i] = 1, 因为字符本身也是一个回文数
radius[i] = 1
while(string[i-radius[i]] == string[i+radius[i]]):
    radius[i] += 1

以上就是Python找回文子串的方法,希望对大家有所帮助。更多Python学习指路:python基础教程

本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。

本站发布的内容若侵犯到您的权益,请邮件联系站长删除,我们将及时处理!


从您进入本站开始,已表示您已同意接受本站【免责声明】中的一切条款!


本站大部分下载资源收集于网络,不保证其完整性以及安全性,请下载后自行研究。


本站资源仅供学习和交流使用,版权归原作者所有,请勿商业运营、违法使用和传播!请在下载后24小时之内自觉删除。


若作商业用途,请购买正版,由于未及时购买和付费发生的侵权行为,使用者自行承担,概与本站无关。


本文链接:https://www.10zhan.com/biancheng/9953.html

标签: Python
分享给朋友:

“【说站】Python找回文子串的方法” 的相关文章

【说站】Thymeleaf报错Error resolving template “XXX”

【说站】Thymeleaf报错Error resolving template “XXX”

修改了一下开源项目的目录结构访问突然报错Error resolving template “XXX”可能原因有如下三种:第一种可能:原因:在使用springboot的过程中,如果使用thymeleaf...

【说站】用一句话就可以去除宝塔面板操作上的二次验证

【说站】用一句话就可以去除宝塔面板操作上的二次验证

用过宝塔的朋友应该都会发现,现在宝塔面板有些鸡肋的功能,删除文件、删除数据库、删除站点等操作都需要做计算题!不仅加了几秒的延时等待,还无法跳过!这时候就会有朋友在想,如何去除宝塔面板的二次验证,此篇文...

【说站】Centos8.0如何配置静态IP详解及永久关闭防火墙

【说站】Centos8.0如何配置静态IP详解及永久关闭防火墙

这篇文章主要介绍了详解Centos8 配置静态IP的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来学习一下!1. 查看自己的网关地址点击虚...

【说站】C#在PDF中添加墨迹注释Ink Annotation的步骤详解

【说站】C#在PDF中添加墨迹注释Ink Annotation的步骤详解

PDF中的墨迹注释(Ink Annotation),表现为徒手涂鸦式的形状;该类型的注释,可任意指定形状顶点的位置及个数,通过指定的顶点,程序将连接各点绘制成平滑的曲线。下面,通过C#程序代码介绍如何...

【说站】Java从resources读取文件内容的方法有哪些

【说站】Java从resources读取文件内容的方法有哪些

本文主要介绍的是java读取resource目录下文件的方法,比如这是你的src目录的结构├── main│ ├── java│ │ └── ...

【说站】linux中redis如何以redis用户重启?

【说站】linux中redis如何以redis用户重启?

通过上图我们可以看到,目前状态是已经以 redis 用户启动着,我想修改下 redis 的密码,然后怎么以 redis 用户重启呢?redis 是 nologin 用户,不能通过 su redis 切...