5. 最长回文子串（中等）

• 难度: 中等
• 考察: 回文数
• 来源: https://leetcode-cn.com/problems/longest-palindromic-substring/
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/5.longest-palindromic-substring.md
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0005-Longest%20Palindromic%20Substring/Article/0005-Longest%20Palindromic%20Substring.md

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2:

输入: "cbbd"
输出: "bb"

思路

核心思想就是两个字“延伸”。

具体来说：

• 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串；
• 如果一个字符串不是回文串，或者在回文串左右分别加不同的字符，得到的一定不是回文串；

关键点

• extend

复杂度

• 时间复杂度：O(N^2)
• 空间复杂度：O(N^2)

代码

func longestPalindrome(s string) string {
    if len(s) <= 0{
        return s
    }

    extend := func(i, j int) string {
        for i >= 0 && j < len(s) && s[i] == s[j] {
            i--
            j++
        }
        return s[i+1:j]
    }

    var logest string
    for i := range s {
        s1 := extend(i, i)
        s2 := extend(i, i+1)
        if len(s1) > len(logest) {
            logest = s1
        }
        if len(s2) > len(logest) {
            logest = s2
        }
    }
    return logest
}