Leetcode（C++）——5. 最長回文子串

5. 最長回文子串

①題目描述

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

②示例

輸入: “babad”

輸出: “bab”

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

輸入: “cbbd”

輸出: “bb”

③解法

方法一：暴力法

周遊字元串每一項，看以此項為中心的最長回文是什麼，選出最長字元串。

class Solution {
public:
    string longestPalindrome(string s) {
    	int max_len = -1;
    	string result = "";
    	int s_length = s.length();
        for(int i = 0; i < s_length; i++) {
        	if(i + 1 < s.length() && s[i] == s[i + 1]) {
        		int tmp_len = 2;
        		int tmp_step = min(i, s_length - i - 2);
        		for(int j = 0; j < tmp_step; j++) {
        			if(s[i - j - 1] == s[i + j + 2]) 
        				tmp_len += 2;
        			else
        				break;
				}
				if(max_len < tmp_len) {
					max_len = tmp_len;
					result = s.substr(i - max_len / 2 + 1, max_len);
				}
			}
			
			int tmp_len = 1;
			int tmp_step = min(i, s_length - i - 1);
			for(int j = 0; j < tmp_step; j++) {
				if(s[i - j - 1] == s[i + j + 1]) 
    				tmp_len += 2;
    			else
    				break;
			}
			if(max_len < tmp_len) {
				max_len = tmp_len;
				result = s.substr(i - max_len / 2, max_len);
			}
			if(i + max_len / 2  >= s_length - 1)
				break;
		}
		return result;
    }
};
           

Leetcode的測試結果：

方法二：中心拓展法

解決了暴力法存在的需要判别回文子串長度為奇數或者偶數的問題，主要通過在相鄰字元串中間加入‘#’，使字元串長度恒為奇數：

class Solution {
public:
    string longestPalindrome(string s) {
    	int s_length = s.length(), max_len = 0, vir_length = 2 * s_length - 1;
    	string result = "";
    	for(int i = 0; i < vir_length; i++) {
    		int tmp_len = i % 2 == 0 ? 1 : 0;
			int tmp_step = min(i, vir_length - i - 1);
    		for(int j = 0; j < tmp_step; j++) {
    			if((i - j - 1) % 2 == 1)
					continue; 
				else {
					if(s[(i - j - 1) / 2] == s[(i + j + 1) / 2]) 
		    			tmp_len += 2;
					else
						break;
				}
			}
			if(max_len < tmp_len) {
				max_len = tmp_len;
				result = s.substr((i - (max_len * 2 - 1) / 2) / 2, max_len); 
			}
			if(i + max_len / 2 - 1 > vir_length)
				break;
		}
		return result;
    }
};
           

Leetcode的測試結果：

方法三：動态規劃

對于任意字元串，如果頭尾字元相同，那麼字元串的最長子序列等于去掉首尾的字元串的最長子序列加上首尾；如果首尾字元不同，則最長子序列等于去掉頭的字元串的最長子序列和去掉尾的字元串的最長子序列的較大者。

class Solution {
public:
    string longestPalindrome(string s) {
        int s_length = s.length();
		if(s_length == 0 || s_length == 1) 
			return s;
        if(s_length == 2) 
			return s[0] == s[1] ? s : s.substr(0, 1);
        bool dp[s_length][s_length];
		int left = 0, right = 0;
        for(int i = s_length - 2; i >= 0; i--) {
			dp[i][i] = 1;
			for(int j = i + 1; j < s_length; j++) {
				dp[i][j] = s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1]);
				if(dp[i][j] && right - left < j - i) {
					left = i;
					right = j;
				}
			}
		}
        //cout<<s<<" "<<s.length()<<" "<<left<<" "<<right - left + 1<<endl;
        string result = s.substr(left, right - left + 1);
        return result;
    }
};
           

Leetcode的測試結果：

方法四：馬拉車算法

複雜度僅為O（n），可以看下原文：原文連結。

class Solution {
public:
	string getC(string s) {
		s = "$" + s + "^";
		string new_s;
		for(int i = 0; i < s.length() * 2 - 1; i++) {
			if(i % 2 == 0)
				new_s += s[i / 2];
			else
				new_s += "#"; 
		}
		return new_s;
	}
    string longestPalindrome(string s) {
    	string new_s = getC(s);
    	cout<<new_s<<endl;
        int s_length = s.length(), v_length = s_length * 2 + 3;
        string result = "";
        int mx = 0, id = 0, max_num = 0, max_pos = 0;
        int p[v_length];
		for(int i = 1; i < v_length - 1; i++) {
			//cout<<getC(s, i);
			p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
			while(new_s[i + p[i]] == new_s[i - p[i]]) {
				p[i]++;
			}
			if(i + p[i] > mx) {
				mx = i + p[i];
				id = i;
			}
			//cout<<" i: "<<i<<" mx: "<<mx<<" p[i]: "<<p[i]<<" id: "<<id<<endl;
			if(max_num < p[i]) {
				max_num = p[i];
				max_pos = i;
			}
		}
		result = s.substr((max_pos - p[max_pos]) / 2, p[max_pos] - 1);
        return result;
    }
};
           

Leetcode的測試結果：

④總結

思路有點多，整理比較麻煩，果然還是菜呀！