最长回文子串

题目描述：

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

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路:

时间复杂度：O(n^2),空间复杂度O()

代码:

func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n+1)

    for i :=0 ;i<=n;i++{
        dp[i] = make([]bool, n+1)
        dp[i][i] = true
    }
    res := string(s[0])
    for L:=2; L<=n;L++{
        for i:=0; i<n; i++{
            j := L + i -1
            if j>=n{
                continue 
            }
            if s[i] == s[j]{
                if j-1 == i{
                    dp[i][j] = true
                }else if  dp[i+1][j-1] == true{
                    dp[i][j] = true
                }
            }

            if dp[i][j] == true{
                if len(res) < j-i+1{
                    res = s[i:j+1]
                }
            }
        }

    }

    return res
}

代码效率：

执行用时：88 ms, 在所有 Go 提交中击败了37.51%的用户
内存消耗：6.7 MB, 在所有 Go 提交中击败了43.11%的用户