LeetCode 5：最長回文子串 動态規劃解法

【傳送門】

題目描述

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: “babad”

輸出: “bab”

注意: “aba” 也是一個有效答案。

示例 2：

輸入: “cbbd”

輸出: “bb”

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/longest-palindromic-substring

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路

• 如果已知從 i+1下标開始到 j-1 下标結束的一個子串是回文的
• 如果第 i 下标的字元等于第 j 下标的字元，那麼從 i 下标開始到 j 下标結束的一個子串是回文的

狀态定義：

// dp[i][i] = 1 表示以下标i開頭，j結尾的子串是回文的 
int dp[MAXLEN][MAXLEN];	
           

狀态轉移方程：

1. dp[i][j] = 1 （當 i==j 時，單個字元是回文的）
2. dp[i][j] = 1 （當 j-i == 1 且 第i下标字元=第j下标字元時，比如 bb 回文）

3. dp[i][j] = 1 （當 i != j 且 j-i>1 且 dp[i+1][j-1]==1

   時，即在一個回文串兩頭加上相同的字元仍然回文）

代碼

class Solution {
public:
    #define MAXLEN 1145
    // dp[i][i] = 1表示以下标i開頭，j結尾的子串是回文的 
    int dp[MAXLEN][MAXLEN];	
    
    string longestPalindrome(string s) 
    {
        int len = s.length();
        // 初始化 
        for(int i=0; i<len; i++)
        {
            for(int j=0; j<len; j++)
            {
                dp[i][j] = 0;
            }
        }
        
        // 長度為1的回文子串是單個字元 
        for(int i=0; i<len; i++)
        {
            dp[i][i] = 1;
        }
        
        // 因為dp[i][j]需要用到dp[i+1][j-1]
        // 故周遊方向：i從大到小，j從小到大 
        for(int i=len-1; i>=0; i--)
        {
            for(int j=i; j<len; j++)
            {
                if(j-i == 1)
                {
                    if(s[i] == s[j])
                    {
                        dp[i][j] = 1;
                    }
                }
                else if(i != j)
                {
                    if(s[i]==s[j] && dp[i+1][j-1]==1)
                    {
                        dp[i][j] = 1;
                    }
                }
            }
        }
        
        // 找最長
        int max = -114514;
        int maxi = 0;
        int maxj = 0;
        for(int i=0; i<len; i++)
        {
            for(int j=0; j<len; j++)
            {
                if(j-i+1>max && dp[i][j]==1)
                {
                    max = j - i + 1;
                    maxi = i;
                    maxj = j;
                }
            }
        }
       
        return s.substr(maxi, maxj-maxi+1);
    }
};
           

附：非leetcode标準（無solution類）的一般代碼

#include <iostream>
#include <string>

using namespace std;
#define MAXLEN 1145
// dp[i][i] = 1表示以下标i開頭，j結尾的子串是回文的 
int dp[MAXLEN][MAXLEN];	

int main()
{
	string s;
	cin>>s;
	int len = s.length();
	
	// 初始化 
	for(int i=0; i<len; i++)
	{
		for(int j=0; j<len; j++)
		{
			dp[i][j] = 0;
		}
	}
	
	// 長度為1的回文子串是單個字元 
	for(int i=0; i<len; i++)
	{
		dp[i][i] = 1;
	}
	
	// 因為dp[i][j]需要用到dp[i+1][j-1]
	// 故周遊方向：i從大到小，j從小到大 
	for(int i=len-1; i>=0; i--)
	{
		for(int j=i; j<len; j++)
		{
			if(j-i == 1)
			{
				if(s[i] == s[j])
				{
					dp[i][j] = 1;
				}
			}
			else if(i != j)
			{
				if(s[i]==s[j] && dp[i+1][j-1]==1)
				{
					dp[i][j] = 1;
				}
			}
		}
	}
	
	int max = -114514;
	int maxi = 0;
	int maxj = 0;
	for(int i=0; i<len; i++)
	{
		for(int j=0; j<len; j++)
		{
			if(j-i+1>max && dp[i][j]==1)
			{
				max = j - i + 1;
				maxi = i;
				maxj = j;
			}
		}
	}
	
	cout<<max<<endl;
	cout<<s.substr(maxi, maxj-maxi+1)<<endl;
	 
	return 0;
}