Leetcode动态规划-5. Longest Palindro

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution:

方法一：动态规划

每个回文子串去掉头尾两个字符仍是回文子串，所以我们假设代表字符串是否是回文子串，则有下述规律：

状态转移方程：

class Solution {
public:
    string longestPalindrome(string s) {
        int s_size = s.size();
        vector<vector<int>> dp(s_size, vector<int>(s_size));    //[1]带括号的初始化指初始化s_size个vector<int>，vector<int>被初始化为s_size个0
        string ans;

        for(int l=0; l<s_size; ++l){
            for(int i=0; i+l<s_size; ++i){
                int j = i + l;
                if(l == 0){
                    dp[i][j] = 1;
                }
                else if(l == 1){
                    dp[i][j] = (s[i]==s[j]);
                }
                else{
                    dp[i][j] = (dp[i+1][j-1] && s[i]==s[j]);
                }
                if(dp[i][j] && l + 1 > ans.size()){
                    ans = s.substr(i, l + 1);
                }
            }
        }
        return ans;
    }
};

Complexity Analysis

• Time complexity : . This gives us a runtime complexity of .
• Space complexity : . It uses . space to store the table.

方法二：中心扩散法

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right){
        while(left >= 0 && right <= s.size() && s[left]==s[right]){
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }   //[2]pair的使用，替换简单的结构体
    
    string longestPalindrome(string s){
        int start = 0;
        int end = 0;
        
        for(int i=0; i<s.size(); ++i){
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i+1);
            if(right1 - left1 > end - start){
                start = left1;
                end = right1;
            }
            if(right2 - left2 > end - start){
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
    
};