5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
具体题目链接

Python（参考leetcode答案）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        lens=len(s)
        t=[[False]*lens for _ in range(lens)]
        #首先先建立矩阵t， (n x n的全为False的矩阵) 用来表示字符串s的每一个子串是否为回文串
        # 回文子串个数 = n + n - 1 + ... + 1,
        # e.g. 字符串babad有5 + 4 + 3 + 2 + 1 = 15种子串。
        # start用来跟踪最长回文子串的起点, max_len代表最长回文子串的长度。
        start, max_len = 0, 1
        # 如果字符串是babad
        # 下面的双循环则进行以下遍历 (遍历所有可能的15个子字符串):
        # b
        # ba,    a
        # bab,   ab,   b,
        # baba,  aba,  ba,  a
        # babad, abad, bad, ad, d
        # dp[left][right]代表s被left和right指针相夹而得的子字符串
        # e.g. left = 0, right = 3, dp[left][right] = baba
        for R in range(len(s)):
            for L in range(0,R+1): 
                span=R-L+1#至少=1
                if s[L]==s[R]:
                    #s[L]==s[R]相同则进行更新t矩阵
                    #此处有两种情况，一种：L=R-1,两数相邻，则判断是否相同。
                    # 另一种L=R，则相当于直接赋值true
                    if span>2:
                        t[L][R]=s[L]==s[R] and t[L+1][R-1]
                    else:
                        t[L][R]=s[L]==s[R] 
                if  t[L][R] and max_len<span:
                    start,max_len=L,span
        return s[start:start+max_len]

思路：通过动态规划解决问题。具体思路可见python代码注释，思路参考文章和官方文档。

GO（参考leetcode答案）

func longestPalindrome(s string) string {
    lens:=len(s)
    t:= make([][]bool, lens)
    start,max_len:=0,1
    for R:=0;R<lens;R++{
        t[R] = make([]bool, lens)
        for L:=0;L<R+1;L++{
            span:=R-L+1
            if s[L]==s[R]{
                if span>2{
                    if s[L]==s[R] && t[L+1][R-1]{
                         t[L][R]=true
                    }
                }else{
                    if s[L]==s[R]{
                         t[L][R]=true
                    }
                }
            }else{
                t[L][R]=false
            }
            if  t[L][R] && max_len<span{
                start,max_len=L,span
            }
        }

    }
    return s[start:start+max_len]
}

思路：思路参考python，但需要注意通过make建立二维数组后，仍需要通过make建立每一个一维数组。