5. Longest Palindromic Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

题意

给定字符串s，求出s的最长回文子串

例子

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

题解

暴力的解法就是O(n^2)遍历所有子串，然后对所有子串进行判断是否是回文，这样这个算法就需要O(n^3)；
对以上的优化就是使用dp，使用一个二维数组来i到j的子串是否构成回文。有以下规则 palind[i][j]=true if j-i<=2 && s[i]==s[j] palind[i][j]=true if j-i>2 && palind[i+1][j-1]

代码

func longestPalindrome(s string) string {
    L := len(s)
    if L == 0 {
        return s
    }
    
    palind := make([][]bool,L)
    for i:=0;i<L;i++{
        palind[i] = make([]bool,L)
    }
    start,end,max := 0,0,0
    for i:=L-1;i>=0;i--{
        for j:=i;j<L;j++{
            if s[i]==s[j] && (j-i<=2 || palind[i+1][j-1]){
                palind[i][j]=true
                if max<(j-i+1){
                    max = j-i+1
                    start = i
                    end = j
                }
            }
        }
    }
    
    return s[start:end+1]
    
}

总结

这道题普通的解法一般都是O(n^2)了，利用dp思想暂存回文结果，即每个子串palind[i][j]要构成回文，必须palind[i+1][j-1]也构成回文。
还有不需要使用二维数组的解法，是通过确定一个中心位置，然后左右遍历寻找回文（没求理解）
还有一种只需要O(n)复杂度的 马拉车算法 https://blog.csdn.net/qq_34374664/article/details/52740377

对dp还是很没有感觉，有想过通过dp来解，但是一般遇到这种题总想着能不能在O(n)的时间内去解决，网上搜了大部分常规解法都是要O(n^2)的。

• ← Previous Post
• Next Post →