Leetcode 5. Longest Palindromic Substring (python)

题目

解法1：动态规划

这边的动态规划需要注意两个点：

• 长度为1和2的需要单独判断
• 二维dp中的一维代表开始，二维代表结束。遍历不能遍历两维，而是遍历长度和其中一维，这样才能保证子问题已经计算

class Solution:def longestPalindrome(self, s: str) -> str:if not s:return ''n = len(s)dp = [[False]*n for _ in range(n)]max_len = 1start = 0# check for substring with length 1 and 2for i in range(n):dp[i][i] = Trueif i<n-1 and s[i]==s[i+1]:dp[i][i+1] = Truemax_len = 2start = i# check for substring with length more than 2for lenth in range(3,n+1):for i in range(n-lenth+1):j = i+lenth-1if dp[i+1][j-1] and s[i] == s[j]:dp[i][j] = Truemax_len = lenthstart = ireturn s[start:start+max_len]

解法2：从中间到两边

根据回文的特性，从中间到两边进行判断。这种解法最直观，复杂度也与解法1一样

class Solution {
    
public:string longestPalindrome(string s) {
    if (s.empty()){
    return "";}int n = s.size();string ans = "";int max_len = 0;int l,r;for (int mid=0;mid<n;mid++){
    // for odd lengthl = mid;r = mid;// expand around midwhile (l>=0 && r<n && s[l] == s[r]){
    if (r-l+1>max_len){
    ans = s.substr(l,r-l+1);max_len = r-l+1;}l--;r++;}// for even lengthl = mid;r = mid+1;while (l>=0 && r<n && s[l]==s[r]){
    if (r-l+1>max_len){
    ans = s.substr(l,r-l+1);max_len = r-l+1;}l--;r++;}}return ans;}
};