5. 最长回文子串

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

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

解答：

  • 动规
    首先确定几个规则：单个字符本身符合回文结构；连续两个字符如果相同，他们也符合回文结构；假设子串起止索引为 i，j 且 s[i] == s[j]，那么他们的回文结构状态应该与 i+1，j-1 的子串相同。
    因此可以得到状态转移方程，我们可以从子串长度为 2 开始求解，向外层拓展。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    func longestPalindrome(s string) string {
    	n := len(s)
    	if n<2 {
    		return s
    	}
    	// 注意结果的初值，第一个字符本身就是回文，可以放到结果中记录
    	res := string(s[0])
    	  
    	dp := make([][]bool, n)
    	for i := range dp {
    		dp[i] = make([]bool, n)
    		// 每个单独的 ch 都是回文结构
    		dp[i][i] = true
    	}
    	  
    	// L 为枚举的子串长度
    	for L:=2; L<=n; L++ {
    		for i:=0; i<n-L+1; i++ {
    			j := i+L-1
    			  
    			if s[i] != s[j] {
    				dp[i][j] = false
    			} else if j-i<3 { // s[i] == s[j] && L<3 // 两个连续相同的 ch 符合回文结构
    				dp[i][j] = true
    			} else {
    				dp[i][j] = dp[i+1][j-1] // 由内向外扩散
    			}
    			  
    			// 是回文，且比以前记录的长，更新
    			if dp[i][j] && j-i+1 > len(res) {
    				res = s[i:j+1]
    			}
    		}
    	}
    	return res
    }