LeetCode Go – 5. 最长回文子串

为了更好的明天，坚持刷 LeetCode！

题目

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
复制代码

示例 2：

输入：s = "cbbd"
输出："bb"
复制代码

示例 3：

输入：s = "a"
输出："a"
复制代码

示例 4：

输入：s = "ac"
输出："a"
复制代码

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
复制代码

解法一 – 动态规划

解题思路

回文字符串即顺着读和反着读都是相同的字符串，所以我们可以认为回文字符串的首字符和尾字符是相等的，即 $s[i] == s[j]$，同样，$s[i+1] == s[j-1]$ 也必须满足。

代码

func longestPalindrome(s string) string {
    l := len(s)
    if l < 2 {
        return s
    }

    r := make([][]bool, l)
    for i := 0; i < l; i++ {
        r[i] = make([]bool, l)
    }

    ml, si := 1, 0
    // 字串长度 sl = j - i + 1
    for sl := 2; sl <= l; sl++ {
        // 左边界 i
        for i := 0; i < l; i++ {
            // 右边界 j - i + 1 = sl
            j := i + sl -1
            if j >= l{
                break
            }
            if s[i] != s[j] {
                r[i][j] = false
            } else {
                if sl <= 3 {
                    r[i][j] = true
                } else {
                    r[i][j] = r[i+1][j-1]
                }
            }

            if r[i][j] && sl > ml {
                ml = sl
                si = i
            }
        }
    }
    return s[si:si+ml]
}
复制代码

执行结果

执行用时：196 ms，在所有 Go 提交中击败了 17.20% 的用户
内存消耗：7.1 MB，在所有 Go 提交中击败了 20.45% 的用户
复制代码

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是字符串的长度。
• 空间复杂度：$O(n^2)$。

题目链接

5. 最长回文子串

相似题目

• 最短回文串
• 回文排列
• 回文对
• 最长回文子序列
• 回文字串