hao同学的技术博客

  • 首页
  • Java
    • Java
    • JVM教程
    • Java面试
    • Java并发入门
    • Java并发进阶
  • 项目
    • 从零打造项目
  • Python
    • Python
    • Python爬虫
    • 算法
  • Java框架
    • Spring
    • SpringBoot
  • 前端
    • Angular
  • 其他
    • Linux
    • SQL
  • 随笔
分享技术,记录人生
一个痴迷于技术的厨艺爱好者
  1. 首页
  2. 算法
  3. 正文

Python 求解最长回文子串

2022年5月22日 189点热度 0人点赞 0条评论

Python 求解最长回文子串插图

前言

题目来源:

记得一副有趣的对联: "雾锁山头山锁雾, 天连水尾水连天", 上联和下联都是回文的.
当然类似的还有: "上海自来水水来自海上, 山西悬空寺寺空悬西山".
回文是什么意思? 就是把内容反过来读也是和原来一样的, 譬如 abccba, xyzyx, 这些都是回文的.
然而我们更感兴趣的是在一个英文字符串 L 中, 怎么找出最长的回文子串.
例如 L = "caayyhheehhbbbhhjhhyyaac", 那么它最长的回文子串是 "hhbbbhh".
这个任务看似简单, 但是如果我告诉你 L 的长度可能会接近 10^4, 问题似乎就变麻烦了.
不管怎么说, 加油吧骚年.

实战分析

网上关于最长回文子串的题型主要包括输出最长回文子串,又或者输出最长回文子串的长度,相对而言,后者更为简单。关于求解方法主要有四种,其一为暴力求解,最为直观,不过时间复杂度也是最大的;其二为动态规划求解,时耗稍微好一点,关于动态规划案例分析,有兴趣的朋友可以去动态规划学习(Python)了解一下;其三是中心扩展;其四是 Manacher 法。关于后两种方法可前往最长回文子串 Python 四种解法进行学习。

本文主要是从另个角度来对题目进行求解,和中心扩展法很像,但是时间复杂度更小。

# L1 = 'caayyhheehhbbbhhjhhyyaac'
# L = 'aabbbaa'
L1 = 'babadcac'

def longestPalindrome():
    '''
    中心扩展
    :return:
    '''
    global L1

    L = L1 + '#'

    maxlen = 0
    start = 0
    start_index_list = []#考虑到最长回文子串存在多个值,这里记录多个起点的索引
    index_dict = {}#用于存放字符串中每个字符连续出现的次数以及起始索引
    for i in range(len(L)):
        if i >= sum(index_dict.values()):
            for j in range(i+1,len(L)+1):
                if len(set(L[i:j])) != 1:
                    index_dict[i] = len(L[i:j-1])
                    break

    for k,v in index_dict.items():
        i = k - 1
        j = k + v
        while i >= 0 and j < len(L):
            if L[i] == L[j]:
                if maxlen < j - i + 1:
                    maxlen = j - i + 1
                    start = i
                elif maxlen == j - i + 1:
                    start_index_list.append(i)
                i -= 1
                j += 1
            else:
                break

    start_index_list.insert(0,start)
    if maxlen >= 2:
        return [L[index:index+maxlen] for index in start_index_list]
    return None

输出结果为:

['hhbbbhh']
['bab', 'aba', 'cac']
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: Python 算法
最后更新:2022年5月22日

hresh

这是一个专注于IT技术学习交流的个人技术博客网站,包括Java学习、Python爬虫、Web开发实践等领域,深耕Java领域,内容涵盖Java基础、Java并发编程、Java虚拟机、Java面试等核心知识点。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

hresh

这是一个专注于IT技术学习交流的个人技术博客网站,包括Java学习、Python爬虫、Web开发实践等领域,深耕Java领域,内容涵盖Java基础、Java并发编程、Java虚拟机、Java面试等核心知识点。

文章目录
  • 前言
  • 实战分析
最新 热点 随机
最新 热点 随机
后端必知:遵循Google Java规范并引入checkstyle检查 Spring Security结合Redis实现缓存功能 Spring Security结合JWT实现认证与授权 Spring Security自定义认证逻辑实现图片验证码登录 Spring Security进阶学习 Spring Security入门学习
Spring之PropertyEditor Python多种方法实现 RSA 加密/解密,签名/验签 Java面试准备之Redis系列一 Python对 BFS(广度优先算法)讲解 关于JVM类加载的那些事 初识Javac编译器和Java语法糖

COPYRIGHT © 2022 hao同学的技术博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

鄂ICP备2022007381号

鄂公网安备 42010302002449号