求最长回文子串

发表于   |   分类于   |  

回文串，就是指正读和反读都一样的字符串，比如"level"或者"noon"等等。

那么，如何求一个字符串的最长回文子串（Longest Palindromic Substring）？这里我们有多种解法。

解法一：暴力法

暴力解法就是直接枚举所有子串，对每个子串判断是否为回文，时间复杂度为$O(n^3)$。

这是最糟糕的方法，相信面试官问你这个问题，绝对不是想要这个答案。

解法二：动态规划法$O(n^2)$

动态规划法是在暴力解法上进行的优化。通过记录一些我们需要的东西，来避免暴力解法中很多重复的判断。

假设 $dp[i][j]$ 表示子串 $s[i…j]$ 是否是回文，那么对于动态规划表 $dp$ 的打表方式如下：

  • 初始化：
    $$\begin{cases}
    dp[i][i] = true & \text{(0 <= i <= n-1)}\\
    dp[i][i-1] = true & \text{(1 <= i <= n-1) }\\
    others = fasle
    \end{cases}$$

  • 动态规划的状态转移方程：
    $$
    dp[i][j] =
    \begin{cases}
    dp[i+1][j-1], & \text{if s[i] == s[j]} \\
    false, & \text{if s[i] ≠ s[j]}
    \end{cases}
    $$

C++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string longestPalindrome(string s) {
	int len = s.size();
	if(len <= 1) return s;
	// 动态规划表，全部初始化为true
	vector<vector<bool>> dp(len, vector<bool>(len, true));

	int start = 0, maxlen = 0;
	for(int k=2; k<=len; ++k) {    // 枚举子串的长度
		for(int i=0; i<=len-k; ++i) {  // 枚举子串起始位置
			int j = i+k-1;
			if(s[i] == s[j] && dp[i+1][j-1])
			{
				dp[i][j] = true;
				start = i;      // 记录回文子串的起点和长度
				maxlen = k;
			}
		}
	}

	return s.substr(start, maxlen);
}

解法三：中心扩展法$O(n^2)$

这个算法思想其实很简单，就是对给定的字符串S，分别以该字符串S中的每一个字符 c 为中心，向两边扩展，记录下以字符 c 为中心的回文子串的长度。时间复杂度为$O(n^2)$，空间复杂度仅为$O(1)$。

但有一点需要注意的是，回文的情况可能是 a b a，也可能是 a b b a。

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
29
// 分别向左右扩展，返回扩展后的字符串
string expand(string s, int left, int right) {
	int len = s.size();
	while (left>=0 && right<len && s[left] == s[right]) 
	{
		left--;
		right++;
	}
	return s.substr(left+1, right-left-1);
}

// 求最长回文子串
string longestPalindrome(string s) {
	int len = s.size();
	if(len<=1) return s;

	string longest;
	for (int i=0; i<len-1; i++) 
	{
		string p1 = expand(s, i, i);  // 奇数
		if (p1.size() > longest.size())
			longest = p1;

		string p2 = expand(s, i, i+1);  // 偶数
		if (p2.size() > longest.size())
			longest = p2;
	}
	return longest;
}





另外，据说还有一个很巧妙的算法，叫Manacher算法，可以在 $O(n)$ 的时间复杂度里求出最长回文子串。由于这个算法我没有研究过，在这里就不介绍了。