目录

  • 1.题目
  • 2.题解
    • C# 解法一：暴力法
    • C# 解法二：动态规划
    • C# 解法三：中心扩展法
    • C# 解法四：马拉车算法

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 为例，讨论一下如何进行中心扩展。
  1. i==2指向c，我们初始化两个指针p与q都指向这个c
  2. p–，q++，p指向了左边b，q指向了右边b
  3. 因为s[p]==s[q], 所以再次执行p–,q++,此时p指向了最左边a，q指向了最右边c
  4. 因为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 " />.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).