LeetCode题库-5.最长回文子串解题方法
回文串解释
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。（百度百科）
简单解法
- 通过上面的解释很容易写出一个判断回文串的逻辑,判断第一位和最后一位是否相同，第二位和倒数第二位是否相同，直到字符串的中部：
1
2
3
4
5
6
7
8
9
10
11
public bool IsHuiWen(string s)
{
for (int i = 0; i < s.Length / 2; i++)
{
if (s[i] != s[s.Length - 1 - i])
{
return false;
}
}
return true;
}
2.对传入的字符串取所有子字符串，依次调用判断逻辑，找到最长的子字符串就行了，为了加快查找速度，我们从最长的子字符串开始，如果要判断的比现在找到的还短那就不用判断了，因为就算是回文串也不是最长的
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
public string LongestPalindrome(string s)
{
var maxLength = 0;
var maxString = "";
for (int i = 0; i < s.Length; i++)
{
if (maxLength > s.Length - i)
{
break;
}
for (int j = s.Length; j > i; j--)
{
if (maxLength > j - i)
{
break;
}
if (IsHuiWen(s.Substring(i, j - i)) && j - i > maxLength)
{
maxLength = j - i;
maxString = s.Substring(i, j - i);
}
}
}
return maxString;
}
无奈重写的算法
上面的解法简单好理解，但是通过不了，因为下面这个字符串判断时超过了leetcode认为的最大时间。 我觉得leetcode的服务器太水了，于是我去看了下推荐答案的时间：3ms。我的算法执行也才800+ms，差值不到1s还是很小的啊。但是没办法还是要改啊。
1
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
第一种是通过遍历子字符串，如果字符串很长（最大1000）遍历的次数还是比较多的，用排列组合可以简单算一下（我不会，反正挺多的），所以还是用最开始想到的方法（因为开始我觉得太麻烦了就没实现）。 从回文串的解释中可以推出，回文串从中间开始向两边推也是相同的，回文串长度可能是奇数或偶数，这两种情况稍有差别，如：bab和baab，中值位置不一样。需要分别考虑（合并考虑我不会）。 这样就可以减少子字符串的截取操作，少一次循环。这样大概在3-4ms左右，比我第一个算法性能提高200倍，还是很牛逼的。
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
public string LongestPalindrome(string s)
{
var maxLength = 0;
var maxStr = "";
for (int i = 0; i < s.Length; i++)
{
var curMaxLength = 1;
while (i - curMaxLength >= 0 && i + curMaxLength < s.Length)
{
if (s[i - curMaxLength] != s[i + curMaxLength])
{
break;
}
curMaxLength++;
}
curMaxLength--;//curMaxLength最后一次是不符合的，所以要去掉最后一次自增
if (maxLength < (curMaxLength * 2 + 1))
{
maxLength = (curMaxLength * 2 + 1);
maxStr = s.Substring(i - curMaxLength , curMaxLength * 2 + 1);
}
curMaxLength = 0;
while (i - curMaxLength >= 0 && i + curMaxLength + 1 < s.Length)
{
if (s[i - curMaxLength] != s[i + curMaxLength + 1])
{
break;
}
curMaxLength++;
}
curMaxLength--;
if (maxLength < (curMaxLength + 1) * 2)
{
maxLength = (curMaxLength + 1) * 2;
maxStr = s.Substring(i - curMaxLength, (curMaxLength + 1) * 2);
}
}
return maxStr;
}
参考资料
本文会经常更新，请阅读原文： https://dashenxian.github.io/post/5.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2 ，以避免陈旧错误知识的误导，同时有更好的阅读体验。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布，但务必保留文章署名 小神仙 （包含链接： https://dashenxian.github.io ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请 与我联系 (125880321@qq.com) 。