5. 最长回文子串

题目

image-20240913213014483

题解

代码

暴力解决

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
30
31
32
33
34
35
36
37
38
39
40
bool isPalindrome(string& s, int left, int right)
{
	while (left < right)
	{
		if (s[left++] != s[right--]) return false;
	}
	return true;
}
 
 
string StringTopic::longestPalindrome(string s)
{
	int n = s.length();
	//长度不够的时候，默认是回文串
	if (n < 2) return s;
 
	//求解最长回文子串
	//滑动窗口
 
	int left = 0, maxLen = 1, right = 1;
	string res(1, s[0]);
 
	for (; left < n - 1; ++left)
	{
		right = left + 1;
		//穷举所有的可能性
		while (right < n)
		{
			if (isPalindrome(s, left, right))
			{
				int temp = maxLen;
				maxLen = max(maxLen, right - left + 1);
				if (temp != maxLen) res = s.substr(left, right - left + 1);
			}
			++right;
		}
	}
 
	return res;
}

动态规划

这个解法的重点在于对之前计算结果的重新使用，并且使用两个参数来确定一个回文串的范围，我在尝试用暴力方法解决的时候没有考虑到这点，往动态规划优化的时候只拿一个参数。

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
30
31
32
33
34
35
36
37
38
39
40
41
string StringTopic::longestPalindrome(string s)
{
	int n = s.length();
	if (n < 2) return s;
 
	vector<vector<int>> memo(n, vector<int>(n));
 
	int left = 0, maxLen = 1;
 
	//所有长度为1 的都是回文串
	for (int i = 0; i < n; i++)
	{
		memo[i][i] = true;
	}
 
	//从小到大堆各个长度进行遍历操作
	for (int L = 2; L <= n; L++)
	{
		for (int i = 0; i < n; i++)
		{
			int j = L + i - 1;
			if (j >= n) break;
 
            //对已经计算出来的回文串的再利用
			if (s[i] != s[j]) memo[i][j] = false;
			else
			{
				if (j - i < 3) memo[i][j] = true; //在长度小于等于3 的时候，只要最两侧的值相等，就可以验证是回文串
				else memo[i][j] = memo[i + 1][j - 1]; //长度大于3的时候就需要看之前的结果了
			}
 
			if (memo[i][j] && j - i + 1 > maxLen)
			{
				maxLen = j - i + 1;
				left = i;
			}
		}
	}
 
	return s.substr(left, maxLen);
}

中心扩张

在最开始是函数位置对以 i 为中心，i i 为中心这两种情况进行扩张，分别对应回文串的的奇数长度和偶数长度，核心的公式就完全和动态规划中判断的方式一致，前提是回文串，最两侧的相等，是回文串，时间复杂度是On2，空间复杂度是O1，实际运行起来比冬天规划快

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
int left = 0;
int maxLen = 0;
 
void Extend(string& s,int i ,int j)
{
	while (i >=0 && j <s.length() && s[i] == s[j])
	{
		if (j - i + 1 > maxLen)
		{
			left = i;
			maxLen = j - i + 1;
		}
		--i;
		++j;
	}
}
 
string StringTopic::longestPalindrome(string s)
{
	for (int i = 0; i < s.length(); i++)
	{
		Extend(s,i,i);
		Extend(s,i,i+1);
	}
 
	return s.substr(left,maxLen);
}

Manacher算法

左神算法——并查集，KMP，Manacher | mao的博客 (mao1mao2mao3mao4.github.io)

左神的内容还是要复习