力扣 5. 最长回文子串 python AC

动态规划

class Solution:def longestPalindrome(self, s):size = len(s)maxl = 1start = 0dp = [[False] * size for _ in range(size)]for i in range(size):dp[i][i] = Truefor L in range(2, size + 1):for i in range(size):j = L + i - 1if j >= size:breakif s[i] == s[j]:if L >= 4:dp[i][j] = dp[i + 1][j - 1]else:dp[i][j] = Trueif dp[i][j] and maxl < L:maxl = Lstart = ireturn s[start:start + maxl]

这里将dp数组含义设为当前位置是否是回文子串

--创建二维dp[i][j]，表示从索引i到索引j位置的子串是否是回文子串（初始值为False）

--将每个单个字符设置为True（长度为1的子串一定是回文子串）

--从2到size遍历L（代表子串长度）（从长度为2开始，因为长度为1的上一步已经标为了True）

  --从0到size-1遍历i（代表子串起点）

    --通过子串长度L和子串起点i求出子串终点（索引为L + i - 1）

    --如果终点超过了整个字符串则退出

    --如果i位置字符和j位置字符相同

      --如果长度大于等于4

        --dp[i][j]是否是回文子串 = dp[i+1][j-1]是否是回文子串

      --否则（长度小于４，即没有更小的区间来推断）

        --dp[i][j] = True

      --判断长度是否比记录过的最大长度最大

        --是的话更新最大长度，并记录此时的起点i

--返回字符串s从start到start+最大长度的子串