Leetcode-5 Longest Palindromic Substring

发表于 | 分类于 | 次

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.

Example 1

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2

1
2
Input: "cbbd"
Output: "bb"

解题思路

回文分两种，一种以字符为对称轴 aba，一种以字符空隙为对称轴 abba。构造回文可以从某个字符或者某个字符空隙开始。因此，可以遍历每个字符或字符空隙，并对其进行扩展，记录下最长的回文子串。

复杂度分析

  • 时间复杂度：$O(n^2)$，遍历每个字符和字符空隙，并对其进行扩展，每次扩展需要$O(n)$时间复杂度。
  • 空间复杂度：$O(1)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		if (n < 2) return s;
		int p = 0, res = 1;
		for (int i = 0; i < n; ++i) {
			int len1 = expandCenter(s, i, i);     //从单个字符开始扩展
			int len2 = expandCenter(s, i, i + 1); //从字符空隙开始扩展
			int len = max(len1, len2);
			if (len > res) {
				res = len;
				p = i - (len - 1) / 2;
			}
		}
		return s.substr(p, res);
	}
private:
	int expandCenter(const string &s, int l, int r) {
		while (l >= 0 && r < s.size() && s[l] == s[r]) {
			--l;
			++r;
		}
		return r - l - 1;
	}
};

改进：Manacher 算法

首先，将两种情况统一为奇数的情况，通过添加 # 字符将原始字符串隔开，得到扩展字符串 es。其次，维护当前访问到的 es 的右边界 mx 及其对应回文的中心位置 id，i 为当前遍历到的位置，p[i] 是以 i 为中心的最长回文子串的半径（包括中心）。

当 i<mx，会出现两种情况：

  1. --mx'--|--j--|---id---|--i--|--mx--
  2. --|-mx'--j----|---id-------i--mx--

第一种情况：p[i]=p[j]；第二种情况，以 j 为中心的回文超出左边界 mx'。若以 i 为中心的回文也超出右边界 mx，则 mx 经过 i 再经过 id 再经过 j 的镜像与 mx' 重叠，意味着右边界应该为 mx+1，与 mx 相矛盾。因此 p[i]=mx-i​。综上 p[i]=min(p[j],mx-i)。

当 i>=mx，继续用扩展法扩展右边界。

时间复杂度：$O(n)$

空间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
string longestPalindrome(string s) {
	int n = s.size(), en = 2 * n + 1; //填充n+1个#字符,使字符总数为奇数
	if (n < 2) return s;
	string es(en, '#');
	for (int i = 0; i < n; ++i) {
		es[2 * i + 1] = s[i]; //原来的字符都以#相隔
	}

	int mx = 1, id = 0;     //当前访问到的es的右边界及其对应回文的中心位置
	int len = 1, start = 0; //s中最长回文子串的长度及其开始位置
	vector<int> p(en, 1);   //存放es中各中心处最长回文子串的半径,包含中心
	for (int i = 0; i < en; ++i) {
		//见博客说明
		p[i] = i < mx ? min(p[2 * id - i], mx - i) : 1;
		//尝试扩张回文子串
		while (i - p[i] >= 0 && i + p[i] < en 
			&& es[i - p[i]] == es[i + p[i]]) ++p[i];
		if (mx < i + p[i]) {
			mx = i + p[i];
			id = i;
		}
		if (p[i] - 1 > len) {
			len = p[i] - 1;
			start = (id - len) / 2;
		}
	}
	return s.substr(start, len);
}