现在的位置: 首页 > 编程技术 > 算法学习 > 正文

求最长回文子串

2015年12月13日 算法学习 ⁄ 共 1495字 ⁄ 字号 求最长回文子串已关闭评论 ⁄ 阅读 752 次

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

那么,如何求一个字符串的最长回文子串(Longest Palindromic Substring)?这里我们有多种解法。

解法一:暴力法

暴力解法就是直接枚举所有子串,对每个子串判断是否为回文,时间复杂度为O(n3)

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

解法二:动态规划法O(n2)

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

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

  • 初始化:

    ⎧⎩⎨dp[i][i]=truedp[i][i1]=trueothers=fasle(0 <= i <= n-1)(1 <= i <= n-1) 
  • 动态规划的状态转移方程:

    dp[i][j]={dp[i+1][j1],false,if s[i] == s[j]if s[i] ≠ s[j]

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(n2)

这个算法思想其实很简单,就是对给定的字符串S,分别以该字符串S中的每一个字符 c 为中心,向两边扩展,记录下以字符 c 为中心的回文子串的长度。时间复杂度为O(n2),空间复杂度仅为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) 的时间复杂度里求出最长回文子串。由于这个算法我没有研究过,在这里就不介绍了。

抱歉!评论已关闭.