为了更好的明天,坚持刷 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. 最长回文子串

相似题目