LeetCode-最长回文子串
Table of Contents
1 Medium-最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
1.1 示例 1：
输入: "babad" 输出: "bab"
注意: "aba"也是一个有效答案。
1.2 示例 2：
输入: "cbbd" 输出: "bb"
2 自己的解答
2.1 思路
- 遍历字符串,然后以当前索引为中心向两边扩展,判断是否为回文.
- 是回文,记录左边界和长度,最后返回子串即可.
2.2 代码
class Solution { public String longestPalindrome(String s) { if (s.length() < 1) { return ""; } // 用作遍历字符串s int i; // 用来记录折半位置 int len; int maxlen = 1; int ms = 0; // 奇数的回文子串 for (i = 0; i < s.length(); i++) { int j = i + 1; int k = i - 1; while (j < s.length() && k >= 0 && s.charAt(j) == s.charAt(k)) { len = j - k + 1; if (len > maxlen) { // 有更长的回文串,记录起始位置 maxlen = len; // 回文从k开始 ms = k; } j++; k--; } } // 偶数的回文子串 for (i = 0; i < s.length(); i++) { int k = i; int j = i + 1; while (j < s.length() && k >= 0 && s.charAt(k) == s.charAt(j)) { len = j - k + 1; if (len > maxlen) { maxlen = len; // 回文从k开始 ms = k; } k--; j++; } } return s.substring(ms, ms + maxlen); }} 3 官方解答
3.1 方法一：最长公共子串
3.1.1 常见错误
- 有些人会忍不住提出一个快速的解决方案，不幸的是，这个解决方案有缺陷(但是可以很容易地纠正)：
- 反转
S，使之变成S'。找到S和S'之间最长的公共子串，这也必然是最长的回文子串。这似乎是可行的，让我们看看下面的一些例子。 - 例如，
S = “caba”, S' =“abac” S以及S′之间的最长公共子串为“aba”，恰恰是答案。- 让我们尝试一下这个例子：
S=“abacdfgdcaba”,S′=“abacdgfdcaba”：S以及S′之间的最长公共子串为“abacd”，显然，这不是回文。
3.2 算法
我们可以看到，当 S 的其他部分中存在非回文子串的反向副本时，最长公共子串法就会失败。为了纠正这一点，每当我们找到最长的公共子串的候选项时，都需要检查子串的索引是否与反向子串的原始索引相同。如果相同，那么我们尝试更新目前为止找到的最长回文子串；如果不是，我们就跳过这个候选项并继续寻找下一个候选。 这给我们提供了一个复杂度为 \(O(n^2)\) 动态规划解法，它将占用 \(O(n^2)\) 的空间（可以改进为使用 \(O(n)\) 的空间）。
3.3 官方解答方法二：暴力法
很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。
3.3.1 复杂度分析
- 时间复杂度：\(O(n^3)\) ，假设
n是输入字符串的长度，则 \(\binom{n}{2} = \frac{n(n-1)}{2}\) 为此类子字符串(不包括字符本身是回文的一般解法)的总数。因为验证每个子字符串需要 \(O(n)\) 的时间，所以运行时间复杂度是 \(O(n^3)\) 。 - 空间复杂度：\(O(1)\) 。
3.4 官方解答方法三：动态规划
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显， “ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。
我们给出 P(i,j) 的定义如下：
\[ P(i,j) = \begin{cases} \text{true,} &\quad\text{如果子串} S_i \dots S_j \text{是回文子串}\\ \text{false,} &\quad\text{其它情况} \end{cases} \]
因此，
\[ P(i, j) = ( P(i+1, j-1) \text{ and } S_i == S_j ) \]
基本示例如下：
\[ P(i, i) = true \]
\[ P(i, i+1) = ( S_i == S_{i+1} ) \]
这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…
3.4.1 复杂度分析
- 时间复杂度： \(O(n^2)\) ， 这里给出我们的运行时间复杂度为 \(O(n^2)\) 。
- 空间复杂度： \(O(n^2)\) ， 该方法使用 \(O(n^2)\) 的空间来存储表。
3.5 官方解答方法四：中心扩展算法
事实上，只需使用恒定的空间，我们就可以在 \(O(n^2)\) 的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 \(2n - 1\) 个这样的中心。
你可能会问，为什么会是 \(2n−1\) 个，而不是 \(n\) 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个 ‘b’ 之间）。
3.5.1 复杂度分析
- 时间复杂度：\(O(n^2)\) ， 由于围绕中心来扩展回文会耗去 \(O(n)\) 的时间，所以总的复杂度为 \(O(n^2)\) 。
- 空间复杂度： \(O(1)\) 。
3.6 官方解答方法五：Manacher 算法
还有一个复杂度为 \(O(n)\) 的 Manacher 算法，你可以在找到详尽的解释。然而，这是一个非同寻常的算法，在45分钟的编码时间内提出这个算法将会是一个不折不扣的挑战。但是，请继续阅读并理解它，我保证这将是非常有趣的。
3.6.1 代码
class Solution { /** * Transform S to T * For example, S = "abba", T="^#a#b#b#a#$". * ^ and $ signs are sentinels appended to each end to avoid bounds check */ public String preProcess(String s) { int n = s.length(); if (n == 0) { return "^$"; } StringBuilder ret = new StringBuilder("^"); for (int i = 0; i < n; i++) { ret.append("#").append(s.charAt(i)); } ret.append("#$"); return ret.toString(); } public String longestPalindrome(String s) { String T = preProcess(s); int n = T.length(); int[] P = new int[n]; // Center point int C = 0; // Right border int R = 0; // first character is $ for (int i = 1; i < n - 1; i++) { // equals to i' = C - (i - C) int iMirror = 2 * C - i; P[i] = (R > i) ? Math.min(R-i, P[iMirror]) : 0; // Attempt to expand palindrome centered at i while(T[i + 1 + P[i]] == T[i - 1 - P[i]]) { P[i]++; } // if palindrome centered at 1 expand past R, // adjust center based on expanded palindrome. if (i + P[i] > R) { C = i; R = i + P[i]; } } // Find the maximum element in P. int maxLen = 0; int centerIndex = 0; for (int i = 1; i < n - 1; i++) { if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; } } return s.substring((centerIndex - 1 - maxLen) / 2, maxLen); }} - 参考文章:
Date: 2018-11-15 15:10
Created: 2018-11-15 四 20:40