搜索
简帛阁>技术文章>最长回文子串看这一篇就够了

最长回文子串看这一篇就够了

大家好,今天我们来聊一聊最长回文子串这个问题。

前几天,有个校招的小伙伴问到了这个问题。今天,我们就来分析一下。

最长回文子串不论是在校招还是社招中都是各大厂出现频率比较高的题目。所以对于正在找工作的同学来说,这是必须要准备的一道题。

Tips:回文串就是正反读都是一样的字符串,比如"上海自来水来自海上"。

问题描述

给你一个字符串 s,找到s中最长的回文子串。
示例:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成

分析问题

一看到这个问题,我们直接从定义出发,这是最容易想到的解决方案。我们把这个“最长回文子串”这几个字,拆开来看,它的要求有三点:“最长”、“回文”、“子串”。首先它是“子串”,然后再“回文”,最后是“最长”。所以,这就很容易理解了,我们把所有的子串求出来,然后判断是不是“回文”,把最长的“回文”拿过来,这个问题不就迎刃而解了。想通这个逻辑,那代码写起来就简单多了。下面我们来看看代码如何实现。

def isPalindromic(ss):
    n=len(ss)
    for i in range(int(n/2)):
        if(ss[i]!=ss[n-i-1]):
            return False
    return True

def longestPalindrome(s):
    ans=""
    maxlen=0
    n=len(s)
    #求出所有子串
    for i in range(n):
        for j in range(i+1,n):
            ss=s[i:j]
            #判断子串是否是“回文”
            if(isPalindromic(ss)):
                #拿出最长的
                if(len(ss)>maxlen):
                    ans=ss
                    maxlen=len(ss)
    return ans

print(longestPalindrome("cbbd"))

这个算法的实现复杂度是O(n^3),空间复杂度是O(1)。那我们有什么优化方式来降低时间复杂度吗?

优化

既然你正反读是一样的,我们把原字符串翻转生成一个新的字符串,然后拿新的字符串和原字符串求最长公共子串不就可以了吗?那我们如何求两个字符串的最长公共子串呢?既然要找公共子串,那不就是求出两个字符串的所有子串,然后比较他们是否相同,找出最长的相同的子串。显而易见,这个算法的时间复杂度也是O(n^3),这不和上面那个算法复杂度一样吗?也没优化上啊。

def longestCommonSubstring(s1,s2):
    n1=len(s1)
    n2=len(s2)
    maxlen=0
    ans=""
    for i in range(n1):
        for j in range(n2):
            length=0
            m=i
            n=j
            while m<n1 and n<n2:
                if s1[m]!=s2[n]:
                    break
                m=m+1
                n=n+1
                length=length+1

            if length> maxlen:
                maxlen=length
                ans=s1[i:i+maxlen]
    return ans

不要着急,我们慢慢往下看。可以先喝口茶休息休息。

有了上面的这个解答,面试官肯定是不满意嘛。要想拿到offer,我们还得加把劲。

我们来看上面的解答有哪些问题呢?我们可以知道在进行子串比较的过程中,多了很多重复的比较。也就是代码里的while循环部分。比如我们在比较以i和j分别为起点的子串时,有可能会进行i+1j+1以及i+2j+2位置的字符的比较。而在比较以 i+1j+1分别为起始点字符串时,这些字符又会被比较一次了。这就说明了该问题有“重叠子问题”的特征,那我们是不是可以用动态规划来解决呢?

我们假设两个字符串分别为s和t,s[i]和t[j]分别表示第i和第j个字符。我们用a[i] [j]表示以s[i]和t[j]为结尾的相同子串的最大长度。那我们就可以很容易推导出a[i+1] [j+1]之间的关系,这两者之间就差a[i+1]和t[j+1]这一对字符,如果a[i+1]和t[j+1]相等,那么a[i+1] [j+1]=a[i] [j] +1,如果不相等,则a[i+1] [j+1]=0。当i=0或者j=0时,对应字符相等的话a[i] [j]=1,不相等的话,则为0。下面,我们来看一下代码如何实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[[0 for _ in range(n)] for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[i][j]=1
                else:
                    a[i][j]=a[i-1][j-1]+1

            if a[i][j] > maxlen:
                maxlen=a[i][j]
                #以i为结尾的子串
                maxend=i

    return s[maxend-maxlen+1:maxend+1]

我们来看下面这个例子S1=“abcedcba”,S2=“abcdecba”。最长的公共子串是“abc”和“cba”,但很明显这不是回文子串。所以,我们在求出最长公共子串后,还需要判断一下该子串倒置前后的下标是否相匹配。比如S1="daba",S2="abad"。S2中aba的下标是0,1,2,倒置前是3,2,1,和S1中的aba的下标符合,所以aba是最长回文子串。其实,我们不需要每个字符都判断,我们只需要判断末尾字符就可以了。

如图所示,我们来看最长公共子串“aba”在翻转前后末尾字符“a”对应的下标分别为i和j。翻转字符串t中该子串的末尾字符“a”对应的下标是j=2,在翻转前s中对应的下标为m=length-1-j=4-1-2=1。m对应的是公共子串在原字符串s中首位字符的下标,再加上子串的长度,即m+a[i] [j]-1对应的是公共子串在原字符串s中末尾字符的下标,如果它和i相等,则说明该子串是回文子串。下面,我们来看一下代码的实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[[0 for _ in range(n)] for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[i][j]=1
                else:
                    a[i][j]=a[i-1][j-1]+1

            if a[i][j] > maxlen:
                #翻转前对应的下标
                m=n-1-j
                #判断下标是否对应
                if m+a[i][j]-1==i:
                    maxlen=a[i][j]
                    maxend=i

    return s[maxend-maxlen+1:maxend+1]

print(longestPalindrome("abacd"))

我们从代码可以看出,时间复杂度为O(n2),空间复杂度也是O(n2)。

我们来看一下空间复杂度还能进行优化吗?

我们来分析一下循环逻辑,i=0,然后遍历j=0,1,2,3。更新一列,然后i=1,再更新一列,更新的时候,我们只需要上一列的信息。所以,我们可以用一个一维数组来保存就好了。我们看一下代码实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[0 for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n-1,-1,-1):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[j]=1
                else:
                    a[j]=a[j-1]+1
            else:
                a[j]=0

            if a[j] > maxlen:
                #翻转前对应的下标
                m=n-1-j
                #判断下标是否对应
                if m+a[j]-1==i:
                    maxlen=a[j]
                    maxend=i

    return s[maxend-maxlen+1:maxend+1]

print(longestPalindrome("abacd"))

所以,我们可以把空间复杂度降低为O(n)。

到此为止,我们就把最长回文子串这个问题说完了。

最后

最长回文子串作为校招和社招中常见的算法题,是需要我们掌握的。对于有“重叠子问题”特征的问题,我们首先要考虑采用动态规划的方法来解决。

今天,我们就聊到这里。更多有趣知识,请关注公众号【程序员学长】。我给你准备了上百本学习资料,包括python、java、数据结构和算法等。如果需要,请关注公众号【程序员学长】,回复【资料】,即可得。

你知道的越多,你的思维也就越开阔,我们下期再见。

大家好,今天我们来聊一聊最长回文子串这个问题。前几天,有个校招的小伙伴问到了这个问题。今天,我们来分析一下。最长回文子串不论是在校招还是社招中都是各大厂出现频率比较高的题目。所以对于正在找工作的同
1概述在工作中总结Hive的常用优化手段和在工作中使用Hive出现的问题。下面开始本篇文章的优化介绍。2介绍首先,我们来看看Hadoop的计算框架特性,在此特性下会衍生哪些问题?数据量大不是问题,数据
目录注册表定制右键菜单前言注册表参数参数和解释验证参数注册表参数总结右击文件菜单配置多级菜单先添加一级菜单再添加二级菜单还可以添加三级菜单看下效果图通过注册表文件创建各种位置的注册表右击桌面空白位置右
Shell是什么?Shell是一个命令解释权,它为用户提供一个向Linux内核发送请求以便运行程序界面系统级程序,用户可以用Shell来启动、挂起、停止甚至是编写一些程序。Shell编程快速入门进
摘要:在本文中,总结开发过程中最为常见的几种MySQL抛出的异常以及如何解决,包括高版本驱动的问题、时区配置问题、SSL连接问题等,是一篇经验总结贴。前言在本文中,总结开发过程中最为常见的几种My
SwiftUI是一种新颖的构建UI方式和全新的编码风格,本文以通俗易懂的语言,从Swift51语法新特性和SwiftUI的优势方面进行分享,希望对热爱移动端的同学有一定的帮助,让大家尽可能快速、全面和
1导入数据library(tidyverse)library(survival)library(survminer)test_datareadtable(survivaltxt,headerT,sep
本文主要介绍如何设计一个高效通用的线程池。详细说明了一个线程池由哪几部分组成,最后通过100行C++代码实现一个高效通用的线程池。1线程池的基础元素std::vector<std::thread
前言公司的移动端业务需要在用户上传图片是由前端压缩图片大小,再上传到服务器,这样可以减少移动端上行流量,减少用户上传等待时长,优化用户体验。插播一下,本文案例已整理成插件,已上传npm,可通过npmi
Netty是Java领域有名的开源网络库,特点是高性能和高扩展性,因此很多流行的框架都是基于它来构建的,比如我们熟知的Dubbo、Rocketmq、Hadoop等,针对高性能RPC,一般都是基于Net