美文网首页
LeetCode-Golang之【5. 最长回文子串】

LeetCode-Golang之【5. 最长回文子串】

作者: StevenChu1125 | 来源:发表于2020-12-09 10:18 被阅读0次

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

    示例 1:

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

    示例 2:

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

    来源:力扣(LeetCode)

    题解

    func longestPalindrome(s string) string {
        n :=len(s)
        dp :=make([][]int,n)
        for i:=0;i<n;i++{
            dp[i] = make([]int,n)
        }
        
        ans := ""
        for k:=0;k<n;k++{
            for i:=0;i+k<n;i++{
                j:=i+k
                if k == 0 {
                    dp[i][j] = 1
                }else if k == 1 {
                    if s[i] == s[j] {
                        dp[i][j] = 1
                    }
                }else {
                    if s[i] == s[j] {
                        dp[i][j] = dp[i+1][j-1]
                    }   
                }
                if dp[i][j] == 1 && k+1 > len(ans){
                    ans = s[i:j+1]
                }
            }
        }
        return ans
    }
    

    相关文章

      网友评论

          本文标题:LeetCode-Golang之【5. 最长回文子串】

          本文链接:https://www.haomeiwen.com/subject/gcmfgktx.html