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/