共计 2955 个字符，预计需要花费 8 分钟才能阅读完成。
点击 这里 能够查看更多算法面试相干内容~
题目形容
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输出：s = “babad” 输入：”bab”
解释：”aba” 同样是合乎题意的答案。
示例 2：
输出：s = “cbbd” 输入：”bb”
示例 3：
输出：s = “a” 输入：”a”
示例 4：
输出：s = “ac” 输入：”a”
提醒：
1 <= s.length <= 1000s仅由数字和英文字母（大写和 / 或小写）组成
奢侈解法
这道题有一个很容易就能想到的简略做法：枚举字符串 s 中的每一位，作为回文串的中心点，左右进行扩大，直到达到边界或者不满足回文串定义为止。
这样做的思路必然是正确的。
但很显然这是一个奢侈（暴力）做法，那么咱们如何确定这一做法是否可行呢？
还记得咱们上一节的剖析思路吗？在【刷穿 LeetCode】4. 寻找两个正序数组的中位数（艰难）当中我向你介绍过，当咱们有了一个简略的实现办法之后，须要从 题目的数据规模 、 计算机的处理速度 和实现办法的计算量 登程，判断这样的做法是否不会超时。
因为字符串长度最多只有 1000，而咱们的实现办法是 O(n^2)，因而咱们算法的计算量应该在 10^6 以内，是在计算机每秒的解决范畴内的。
首先枚举回文串的核心 i，而后分两种状况向两边扩大边界，直到达到边界或者不满足回文串定义为止：
- 回文串长度是奇数，则顺次判断
s[i − k] == s[i + k], k = 1,2,3… - 回文串长度是偶数，则顺次判断
s[i − k] == s[i + k − 1], k = 1,2,3…
class Solution {public String longestPalindrome(String s) {
String ans = "";
for (int i = 0; i < s.length(); i++) {
// 回文串为奇数
int l = i - 1, r = i + 1;
String sub = getString(s, l, r);
if (sub.length() > ans.length()) ans = sub;
// 回文串为偶数
l = i - 1;
r = i + 1 - 1;
sub = getString(s, l, r);
if (sub.length() > ans.length()) ans = sub;
}
return ans;
}
String getString(String s, int l, int r) {while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}工夫复杂度：先枚举了 s 中的每个字符作为回文串的中心点，再从中心点登程左右扩大，最多扩大到边界。复杂度是 $O(n^2)$
空间复杂度：$O(1)$
Manacher 算法
这是一个比拟冷门的算法，应用范畴也比拟繁多，只能用于解决「回文串」问题。
Manacher 的确是「回文串」问题的最优解。
但即便是 LeetCode 上所有对于「回文串」的问题，没有一道是必须通过 O(n) 的 Manacher 算法能力 AC。
因而我这里间接给解决方案（能够间接当做模板来应用），而不再探讨算法的具体实现原理。
Manacher 算法较长，为了防止回文串长度奇偶问题的分状况探讨，我会对原字符进行解决，在边界和字符之间插入占位符。
应用了这样的技巧之后，当非占位字符作为回文串的核心时，对应了回文串长度为奇数的状况；当占位字符作为回文串的核心时，对应了回文串长度为偶数的状况。。
举个例子：
原字符：”babad”，转换后：”*b*a*b*a*d*”，失去的回文串：”*b*a*b*”，而后再去除占位符输入：”bab”。
解释：”aba” 同样是合乎题意的答案。
class Solution {public String longestPalindrome(String s) {if (s.length() == 1) return s;
char[] chars = manacherString(s);
int n = chars.length;
int[] pArr = new int[n];
int C = -1, R = -1, pos = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {pArr[i] = i < R ? Math.min(pArr[C * 2 - i], R - i) : 1;
while (i + pArr[i] < n && i - pArr[i] > -1) {if (chars[i + pArr[i]] == chars[i - pArr[i]]) {pArr[i]++;
} else {break;}
}
if (i + pArr[i] > R) {R = i + pArr[i];
C = i;
}
if (pArr[i] > max) {max = pArr[i];
pos = i;
}
}
int offset = pArr[pos];
StringBuilder sb = new StringBuilder();
for (int i = pos - offset + 1; i <= pos + offset - 1; i++) {if (chars[i] != '#') sb.append(chars[i]);
}
return sb.toString();}
char[] manacherString(String s) {char[] chars = new char[s.length() * 2 + 1];
for (int i = 0, idx = 0; i < chars.length; i++) {chars[i] = (i & 1) == 0 ? '#' : s.charAt(idx++);
}
return chars;
}
}工夫复杂度：只对字符串进行了一次扫描。复杂度为 $O(n)$
空间复杂度：$O(1)$
总结
明天这道题目，三叶除了提供惯例的、工夫复杂度为 $O(n^2)$ 的奢侈解法以外，还给你提供了对于「回文串」的最优解 Manacher 算法模板，倡议有余力的同学能够背过。
背过这样的算法的意义在于：相当于大脑里有了一个工夫复杂度为 $O(n)$ 的 api 能够应用，这个 api 传入一个字符串，返回该字符串的最大回文子串。
同时借助 Manacher 算法，还给大家介绍了如何防止回文串长度的分状况探讨，这个技巧只有波及「回文串」问题都实用（无论是否应用 Manacher 算法）。
对于想要背过 Manacher 算法的同学，倡议先敲 3 遍，默写 2 遍，而后过了 24 小时，再默写 2 遍，一周后，再进行反复，直到纯熟。
不要胆怯忘记，忘记是失常的，多进行几次反复便会造成肌肉记忆。LeetCode 周赛上长年占据第一页的选手，无不都是对算法套路和模板极其纯熟。加油 ~
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.5 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
因为 LeetCode 的题目随着周赛 & 双周赛一直减少，为了不便咱们统计进度，咱们将依照系列起始时的总题数作为分母，实现的题目作为分子，进行进度计算。以后进度为 5/1916。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：Github 地址 & Gitee 地址。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其余的优选题解。