LeetCode -- 5.最長回文子串

連結：最長回文子串

描述：

給你一個字元串 s，找到 s 中最長的回文子串。

輸入：s = “babad”

輸出：“bab”

解釋：“aba” 同樣是符合題意的答案。

輸入：s = “a”

輸出：“a”

兩種解法

• 動态規劃
• • 思路
  • 代碼
• 中心擴充算法
• • 思路

動态規劃

思路

回文串的頭尾去掉之後依舊是一個回文串，由此可以這樣擴充，咱們用二位數組一維化寫出一個僞遞歸式，本質是一個真值表。

狀态方程：P(i,j)=P(i+1,j−1)∧(Si​==Sj​）

意思是原頭尾相同，且前後各擴充一個也能相同

代碼

class Solution {
public:
    string longestPalindrome(string s) {
    	int n = s.size();
    	vector<vector<int>> dp(n, vector<int>(n)); //實際上做的是一個TF表 
    	string ans;
		for(int l = 0; l < n ; ++l)
		{
		    for(int i = 0; i + l < n ; ++i)
	    	{
	    		int j = i + 1;
	    		if(l == 0) //空串滿足 
	    		{
	    			dp[i][j] = 1;
				}
				else if(l == 1) //單一字元滿足 
				{
					dp[i][j] = (s[i] == s[j]);
				}
				else //第一個字元與最後一個相同，擴充後最後一個和第一個相同（将遞歸數組化） 
				{
					dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
				}
				if(dp[i][j] && l + 1 > ans.size()) //長度大于上一輪檢測到的回文串，更新 
				{
					ans = s.substr(i, l+1); //從下标為i處開始截取l+1個字元 
				}
			}	
		}
		return ans;
	}
};
           

時間和空間都花費了太多，換個辦法。

中心擴充算法

思路

周遊每一個索引，以這個索引為中心，利用“回文串”中心對稱的特點，往兩邊擴散，看最多能擴散多遠。但是這個中心有兩種情況：

• 回文串長度為奇數，中心是一個具體的字元
• 回文串長度為偶數，中心是一個空字元

這樣看，回文串的中心一共有2n-1個

class Solution {
public:
	string longestPalindrome(string s) 
	{
		if (s.length() < 1)
		{
			return "";
		}
		int start = 0, end = 0;
		for (int i = 0; i < s.length(); i++)
		{
			int len1 = expandAroundCenter(s, i, i);//一個元素為中心
			int len2 = expandAroundCenter(s, i, i + 1);//兩個元素為中心
			int len = max(len1, len2);
			if (len > end - start)
			{
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substr(start, end - start + 1);
	}

	int expandAroundCenter(string s, int left, int right)
	{
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s[L] == s[R])
		{// 計算以left和right為中心的回文串長度
			L--;
			R++;
		}
		return R - L - 1;
	}
};
           

在此不多說，這是一個很好的動态規劃問題（雖然時間和空間上撈了點），可以掌握好後舉一反三。