1.题目
给你一个字符串 s，找到 s 中最长的回文子串。
- 示例1:
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
- 示例 2：
输入：s = "cbbd" 输出："bb"
- 提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母组成
2.题解
- 首先我们会想到使用 暴力法 来解决题目，用3层循环来对每个子串进行检查，最后取最长的子串作为结果，这样时间复杂度为 O(n^3) 。然后可能会考虑到使用动态规划的方式，以空间来换取时间,可以将时间复杂度优化为 O(n^2)，但相应的空间复杂度会增大。在仔细分析 回文串 的特点后，会想到使用 中心扩展法 ，该方法对于该题目来说不失为一种优秀的解决方法，时间复杂度为 O(n^2)，空间复杂度为 O(1) ; 最后，还介绍了马拉车算法 Manacher ，这是一种非同寻常的算法，充分利用了 回文 的特点， 不可思议的将时间复杂度降为了 O(n) .
C# 解法一：暴力法
- 使用 3层循环 来依次对所有子串进行检查，将最长的子串最为最终结果返回。下面代码中，我们检查i到j的子串是否是回文串，如果是 且长度大于当前结果result的长度，就将result更新为i到j的子串。
public class Solution { public string LongestPalindrome(string s) { string result = ""; int n = s.Length; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // 检查 s[i]到s[j]是否是回文串，如果是，且长度大于result长度，就更新它 int p = i, q = j; bool isPalindromic = true; while (p < q) { if (s[p++] != s[q--]) { isPalindromic = false; break; } } if (isPalindromic) { int len = j - i + 1; if (len > result.Length) { result = s.Substring(i, len); } } } } return result; } }
- 时间复杂度：O(n^3)
- 3层循环，所以是 O(n^3) .
- 空间复杂度：O(1)
- 仅使用了几个变量来存值，所以为 O(1) .
C# 解法二：动态规划
- 方法一中，存在大量的重复计算工作，例如当 s=“abcba” 时, 对于子串 “bcb” 和 子串 “abcba”, 分别进行了2次完整的计算，来检测该子串是否是回文串。
很明显的是，对于 s=“abcba” , 在已知 "bcb"是回文串的情况下，要判断 "bcb"是否是回文串的话，只需要判断两边的*位置的字符是否相等即可。 我们定义 P(i,j) 表示 s[i,j]是否是回文串，若s[i,j]是回文串，则P(i,j)=true,否则为false. 则有下面的递推公式成立：
P[i,j] = p(i+1,j-1) && ( s[i]==s[j] )
- 对于上面公式有2个特殊情况，当子串长度为1或2时，上面公式不成立。我们单独分析这两种情况：
若子串长度为1，即 j==i, 则 P[i,j] = P[i,i] = true； 若子串长为2，即j==i+1, 则 P[i,j] = P[i,i+1] = ( s[i]==s[i+1] )
- 在实际执行时，我们先求所有长度为1的子串的P值，再求所有长度为2的子串的P值，之后再求长度3的，以此类推，一直到长度为s.Length的
public class Solution { public string LongestPalindrome(string s) { int n = s.Length; bool[,] P = new bool[n, n]; string result = ""; //遍历所有的长度 for (int len = 1; len <= n; len++) { for (int start = 0; start < n; start++) { int end = start + len - 1; if (end >= n) //下标已经越界，结束本次循环 break; //长度为 1 和 2 的单独判断下 P[start, end] = (len == 1 || len == 2 || P[start + 1, end - 1]) && s[start] == s[end]; if (P[start, end] && len > result.Length) { result = s.Substring(start, len); } } } return result; } }
- 时间复杂度：O(n^2)
- 两层循环，所以是 O(n^2)
- 空间复杂度：O(n^2)
- P是二维数组，所以是 O(n^2)
C# 解法三：中心扩展法
- 对于回文串，我们可以找到一个中心，从这个中心向两边扩展的话，两边对应的值是相等的。按照这个逻辑，我们只需要一层主循环 i 将 s 遍历一遍即可,并在循环内部 将s[i]视为中心 使用中心扩展法来求出以s[i]为中心的最长的回文串；当i将s遍历完后，即可得到s的最长回文串。
下面我们以 s=“abcbc”, 且 i==2 为例，讨论一下如何进行中心扩展。
- i==2指向c，我们初始化两个指针p与q都指向这个c
- p–，q++，p指向了左边b，q指向了右边b
- 因为s[p]==s[q], 所以再次执行p–,q++,此时p指向了最左边a，q指向了最右边c
- 因为s[p]!=s[q],所以结束扩展。
public class Solution { public string LongestPalindrome(string s) { string result = ""; int n = s.Length; int end = 2 * n - 1; for (int i = 0; i < end; i ++) { double mid = i / 2.0; int p = (int)(Math.Floor(mid)); int q = (int)(Math.Ceiling(mid)); while (p >= 0 && q < n) { if (s[p] != s[q]) break; p--; q++; } int len = q - p - 1; if (len > result.Length) result = s.Substring(p + 1, len); } return result; } }
- 时间复杂度：O(n^2)
- 主循环执行约2n次，内部while最多执行约n/2次（从s最中心向外扩展到s头和s尾），所以复杂度为 O(n^2).
- 空间复杂度：O(1)
- 仅使用了几个变量来存值，所以空间复杂度为O(1)
C# 解法四：马拉车算法
- 马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫 Manacher 的人在 1975 年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性。
首先我们需要解决s长度可能为奇数或偶数的问题。在每个字符间插入 “#”，经过处理，字符串的长度永远都是奇数了
public class Solution { public string PreProcess(string s) { string t = "^"; int n = s.Length; if (n == 0) return "^$"; for (int i = 0; i < n; i++) { t += "#" + s[i]; } t += "#$"; return t; } // 方法四：马拉车算法 108ms,26.4M public string LongestPalindrome(string s) { string t = PreProcess(s); int n = t.Length; int[] p = new int[n]; int c = 0, r = 0; //计算P for (int i = 1; i < n - 1; i++) { int j = 2 * c - i; //情况2和3可以总结为 p[i]= min(r - i + 1, p[j]) ,情况1为 p[i]=1; p[i] = r > i ? Math.Min(r - i + 1, p[j]) : 1; //对于情况4和1，直接扩展即可； //对于情况2和3，也可以直接扩展；虽然一定扩展不了，但是这样的计算过程比“判断是情况2或3”的计算量还要小，仔细品味 while (t[i - p[i]] == t[i + p[i]]) { p[i]++; } if (i + p[i] > r) { //找到了更长的回文串，更新c和r c = i; r = i + p[i] - 1; } } // 找出 P 的最大值 int maxLen = 0; int centerIndex = 0; for (int i = 1; i < n - 1; i++) { int len = p[i] - 1; if (len > maxLen) { maxLen = len; centerIndex = i; } } int start = (centerIndex - maxLen) / 2; return s.Substring(start, maxLen); } }
- 时间复杂度：O(n)
- 空间复杂度：O(n)
- 因为p数组空间复杂度为 O(n).
