0005. 最长回文子串

[utterances-bot]

0005. 最长回文子串 | 算法通关手册

5. 最长回文子串 # 标签：字符串、动态规划 难度：中等 题目大意 # 给你一个字符串 s，找到 s 中最长的回文子串。 解题思路 # 可以用动态规划来做。主要是定义

https://algo.itcharge.cn/Solutions/0001-0099/longest-palindromic-substring/

[jianghongcheng]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ''
        for i in range (len(s)):
            start = max(0, i - len(res) - 1)
            temp = s[start : i + 1]
            if temp == temp[:: -1]:
                res = temp
            else:
                temp = temp[1:]
                if temp == temp[::-1]:
                    res = temp
        return res

[S1mpleBug]

附上C++代码

关于DP的做法，🔗官方题解视频05:34处有说明。和上述题解思路一致。

class Solution {
public:
    string longestPalindrome(string s) {
        bool dp[N][N] = {false};
        int n = s.size();
        if(n <= 1) return s;
        int maxlen = 1;
        int start = 0;
        for(int j = 1; j < n; ++j) {
            for(int i = 0; i < j; ++i) {
                if(s[i] == s[j]) {
                    if(j-i+1 < 4) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }

                if(dp[i][j] && j-i+1 > maxlen) {
                    maxlen = j-i+1;
                    start = i;
                }
            }
        }
        return string(s.begin()+start, s.begin()+start+maxlen);
    }
};

[gxysimon]

class Solution: def longestPalindrome(self, s: str) -> str: res = '' for i in range (len(s)): start = max(0, i - len(res) - 1) temp = s[start : i + 1] if temp == temp[:: -1]: res = temp else: temp = temp[1:] if temp == temp[::-1]: res = temp return res

您好 请问能解释一下这段代码吗…我实在是没搞懂，谢谢！！