Python刷leetcode--5.最长回文子串

重点：

1.

if tmp > maxLen and s[i] == s[i-tmp+1]:

判断最后一位和第一位是不是相等，相等才是回文串。

2.

动态规划，初始化dp数组，注意多定义一位，方便加。 预计0是’’ 字符

3.

递推方程

dp[i+1][j+1] = dp[i][j] + 1

class Solution:
    def longestPalindrome(self, s: str) -> str:
# leetcode submit region end(Prohibit modification and deletion)
        # 状态数组  dp[n+1][n+1]
        n = len(s)
        dp = [([0] * (n+1)) for _ in range(n+1)]
        maxLen = 0
        maxEnd = 0
        s2 = s[::-1]
        for i in range(n):
            for j in range(n):
                if s[i] == s2[j]:
                    tmp = dp[i+1][j+1] = dp[i][j] + 1  # 用tmp代替当前状态值
                    if tmp > maxLen and s[i] == s[i-tmp+1]:
                        maxLen = tmp
                        maxEnd = i
        return s[maxEnd-maxLen+1: maxEnd+1]
           

类似的题目：

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zhe-yao-jie-shi-ken-ding-jiu-dong-liao-by-hyj8/