博客

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的测试结果：

④总结

思路有点多，整理比较麻烦，果然还是菜呀！