esc to dismiss

5. 最长回文子串

题目

给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

示例 3:

输入:s = "a"
输出:"a"

示例 4:

输入:s = "ac"
输出:"a"

解题思路

字符串算法 算法其实就是将一系列算法融会贯通,本题解题思路有两种。

一种是从字符串中间开始向外扩展,LeetCode题解中称之为 中心扩展算法

另一种是 动态规划 ,其关键点在于得到状态转移方程,如果知道本题要用 动态规划来做,状态转移方程也是比较容易想到的,即外层字符串的回文等于内层字符串的回文+两端字符比较:

dp[i][i+span-1] = dp[i+1][i+span-2] && s[i] == s[i+span-1]

全部代码如下:

func longestPalindrome(s string) string {
    size := len(s)
    dp := make([][]bool, size, size)
    for i := 0; i < size; i++ {
        dp[i] = make([]bool, size, size)
        dp[i][i] = true
    }

    start := 0
    maxSpan := 1
    for span := 2; span <= size; span++ {
        for i := 0; i <= size-span; i++ {
            if span == 2 {
                dp[i][i+span-1] = s[i] == s[i+span-1]
            } else {
                dp[i][i+span-1] = dp[i+1][i+span-2] && s[i] == s[i+span-1]
            }

            if dp[i][i+span-1] {
                start = i
                maxSpan = span
            }
        }
    }

    return s[start : start+maxSpan]
}

经验教训

略。

x