当前位置：首页 > news >正文

LeetCode0005.最长回文子串 Go语言AC笔记

news 来源：原创 2024/5/6 1:12:54

时间复杂度：O(n²)

解题思路

动态规划经典题型！

该题可以用多种方法解决，即使用动态规划解决也有多种方法，但我用的这个动态规划解法绝对是最容易理解的！

令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为true，不是则为false。这样根据S[i]是否等于S[j]，可以把转移情况分为两类：

若S[i]==S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]也不是回文子串。
若S[i]!=S[j]，那么S[i]至S[j]一定不是回文子串。

由此可以写出状态转移方程：

$dp[i][j]= \begin{cases} &dp[i+1][j-1], \text{ } S[i]==S[j] \\ & 0,\text{ } S[i]!=S[j] \end{cases}$

边界：dp[i][j]=1,dp[i][i+1]=(S[i]==S[i+1])?true:false。

到这里还有一个问题没有解决，那就是如果按照i和j从小到大的顺序来枚举子串的两个端点，然后更新dp[i][j]，会无法保证dp[i+1][j-1]已经被计算过，从而无法得到正确的dp[i][j]。

比如下面这个例子：

如上图所示，先固定i==0，然后枚举j从2开始。当求解dp[0][2]时，精会转换为dp[1][1]，而dp[1][1]是在初始化中得到的；当求解dp[0][3]时，将会转换为dp[1][2]，而dp[1][2]也是在初始化中得到的；当求解dp[0][4]时，将会转换为dp[1][3]，但是dp[1][3]并不是已经计算过的值，因此无法状态转移。事实上，无论对i和jd枚举顺序做何调整，都无法调和这个矛盾，因此必须想办法寻找新的枚举方式。

根据递推写法从边界出发的原理，注意到边界表示的是长度为1和2的子串，且每次转移时都对子串的长度减了1，因此不妨考虑按子串的长度和子串的初始位置进行枚举，即第一遍将长度为3的子串的dp值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp值……这样就可以避免状态无法转移的问题。

如上图所示，可以先枚举子串长度L（注意：L是可以取到整个字符串的长度len(S)的），再枚举左端点i，这样右端点i+L-1也可以直接得到。

AC代码

func longestPalindrome(s string) string {
    res:=s[0:1]
    n:=len(s)
    dp:=make([][]bool,n)
    for i:=0;i<len(dp);i++{
        dp[i]=make([]bool,n)
    }
    //创建边界条件
    for i:=0;i<n-1;i++{
        dp[i][i]=true
        //长度为2的回文子串
        if s[i]==s[i+1]{
            dp[i][i+1]=true
            if len(res)==1{
                res=s[i:i+2]
            }
        }
    }
    //从长度为3的回文子串开始
    for l:=3;l<=n;l++{
        //左端点为i
        for i:=0;i+l-1<n;i++{
            j:=i+l-1//子串右端点
            if s[i]==s[j]&&dp[i+1][j-1]{
                dp[i][j]=true
                if l>len(res){
                    res=s[i:j+1]
                }
            }
        }
    }
    return res
}