• 技术文章 >Python技术 >Python基础教程

    Python找回文子串的方法

    小妮浅浅小妮浅浅2021-06-15 10:37:16原创4411

    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电脑。

    专题推荐:python
    上一篇:python json保存数据的方法 下一篇:Python中Exchange发邮件

    相关文章推荐

    • Python Elasticsearch DSL如何使用• Python中deque的操作整理• Python命令行如何运行文件• Python字典和json的比较• python代码提速有哪些方法• python如何转移数据库里的数据• python字符串如何取值• python切片步长怎样实现• python字符串格式化的方法整理• python语句和缩进的实现• python变量如何拼接• python常量是什么

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网