leetcode:5.最長回文子串

最長回文子串

題目描述

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

示例 1：

輸入: “babad”

輸出: “bab”

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

示例 2：

輸入: “cbbd”

輸出: “bb”

解法一

暴力枚舉，枚舉每一個子串，并驗證其是否為回文子串。

解法二：動态規劃

令dp[i][j]表示從第i個字元到第j個字元的子串是否為回文子串。狀态轉移方程為：

邊界條件為：

然後進行狀态轉移即可。

解法三：中心擴散

注意到每一個回文子串都是從單一字元或兩個相同字元向四周擴散而來，是以隻需要驗證對稱子串即可。

代碼一

class Solution {
public:
	string longestPalindrome(string s) {
		int len = s.length();
		string result = "";
		if (len == 0)   return result;
		//if (len == 1)   return s;
		for (int i = len; i >= 1; i--)
		{
			for (int j = 0; j <= len - i; j++) {
				if (isPalindrome(s, j, j + i - 1))
				{
					for (int m = j; m <= j + i - 1; m++) {
						result += s[m];
					}
					return result;
				}
			}
		}
		return result;

	
	}
	bool isPalindrome(string s,int start,int end) {
		string pre = "";
		for (int i = start; i <= end; i++)
		{
			pre += s[i];
		}
		string rever = "";
		for (int i = end-start; i >= 0; i--)
		{
			rever += pre[i];
		}
		return (pre == rever);
	}
};
           

代碼二

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n));
        string ans;
        for(int l = 0;l<n;++l){
            for(int i = 0;i+l<n;++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] = ((s[i] == s[j]) && dp[i+1][j-1]);
                if(dp[i][j] && l+1>ans.size()) ans = s.substr(i,l+1);
            }
        }
        return ans;
    }
};
           

代碼三

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
        int l,r;
        string ans;
        for(int i = 0;i<n;++i){
            l = i-1;r = i+1;
            while(l>=0&&r<n){
                if(s[l]!=s[r]) break;
                --l;++r;
            }
            if(r-l-1>ans.size()) ans = s.substr(l+1,r-l-1);
        }
        for(int i = 0;i<n-1;++i){
            if(s[i] == s[i+1]){
                l = i-1;r = i+2;
                while(l>=0&&r<n){
                if(s[l]!=s[r]) break;
                --l;++r;
                }
                if(r-l-1>ans.size()) ans = s.substr(l+1,r-l-1);
            }
        }
        return ans;
    }
};