LeetCode Longest Palindromic Substring

LeetCode Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.


这题要求我们找出一个字符串S中的最长回文子串,之前在hihoCoder 1032-最长回文子串就详细讨论过相关问题,这里就不再赘述了,代码完全一样,如下:

class Solution {
public:
	string preProcess(string s)
	{
		int n = s.size();
		if (n == 0)
			return "^#";
		string ret = "^";
		for (int i = 0; i < n; i++)
			ret += "#" + s.substr(i, 1);
		return ret + "#$";
	}
	string longestPalindrome(string s) {
		string t = preProcess(s);
		vector<int> p(t.size(), 0);
		int c = 0, r = 0, n = t.size();
		for (int i = 1; i < n - 1; i++)
		{
			int i_mirror = 2 * c - i;
			p[i] = (r > i) ? min(p[i_mirror], r - i) : 0;
			while (t[i + p[i] + 1] == t[i - p[i] - 1])
				p[i]++;
			if (i + p[i] > r)
			{
				c = i;
				r = i + p[i];
			}
		}
		
		int maxLen = 0, centerIndex = 0;
		for (int i = 1; i < n - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		
		return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
	}
};

本代码提交AC,用时12MS,击败了73%的CPP用户,看来效率不错,估计中心扩展法O(n^2)也能过。

Leave a Reply

Your email address will not be published. Required fields are marked *