共计 1641 个字符，预计需要花费 5 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
5. 最长回文子串
———–
回文串是面试经常遇到的问题（尽管问题自身没啥意义），本文就通知你回文串问题的核心思想是什么。
首先，明确一下什：回文串就是正着读和反着读都一样的字符串。
比如说字符串 aba 和 abba 都是回文串，因为它们对称，反过来还是和自身一样。反之，字符串 abac 就不是回文串。
能够看到回文串的的长度可能是奇数，也可能是偶数，这就增加了回文串问题的难度，解决该类问题的外围是 双指针。上面就通过一道最长回文子串的问题来具体了解一下回文串问题：
string longestPalindrome(string s) {}一、思考
对于这个问题，咱们首先应该思考的是，给一个字符串 s，如何在 s 中找到一个回文子串？
有一个很乏味的思路：既然回文串是一个正着反着读都一样的字符串，那么如果咱们把 s 反转，称为 s'，而后在 s 和 s' 中寻找 最长公共子串，这样应该就能找到最长回文子串。
比如说字符串 abacd，反过来是 dcaba，它的最长公共子串是 aba，也就是最长回文子串。
然而这个思路是谬误的，比如说字符串 aacxycaa，反转之后是 aacyxcaa，最长公共子串是 aac，然而最长回文子串应该是 aa。
尽管这个思路不正确，然而 这种把问题转化为其余模式的思考形式是十分值得提倡的。
上面，就来说一下正确的思路，如何应用双指针。
寻找回文串的问题核心思想是：从两头开始向两边扩散来判断回文串。对于最长回文子串，就是这个意思：
for 0 <= i < len(s):
找到以 s[i] 为核心的回文串
更新答案然而呢，咱们方才也说了，回文串的长度可能是奇数也可能是偶数，如果是 abba这种状况，没有一个核心字符，下面的算法就没辙了。所以咱们能够批改一下：
for 0 <= i < len(s):
找到以 s[i] 为核心的回文串
找到以 s[i] 和 s[i+1] 为核心的回文串
更新答案PS：读者可能发现这里的索引会越界，等会会解决。
二、代码实现
依照下面的思路，先要实现一个函数来寻找最长回文串，这个函数是有点技巧的：
string palindrome(string& s, int l, int r) {
// 避免索引越界
while (l >= 0 && r < s.size()
&& s[l] == s[r]) {
// 向两边开展
l--; r++;
}
// 返回以 s[l] 和 s[r] 为核心的最长回文串
return s.substr(l + 1, r - l - 1);
}为什么要传入两个指针 l 和 r 呢？因为这样实现能够同时解决回文串长度为奇数和偶数的状况：
for 0 <= i < len(s):
# 找到以 s[i] 为核心的回文串
palindrome(s, i, i)
# 找到以 s[i] 和 s[i+1] 为核心的回文串
palindrome(s, i, i + 1)
更新答案上面看下 longestPalindrome 的残缺代码：
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i++) {// 以 s[i] 为核心的最长回文子串
string s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为核心的最长回文子串
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}至此，这道最长回文子串的问题就解决了，工夫复杂度 O(N^2)，空间复杂度 O(1)。
值得一提的是，这个问题能够用动静布局办法解决，工夫复杂度一样，然而空间复杂度至多要 O(N^2) 来存储 DP table。这道题是少有的动静布局非最优解法的问题。
另外，这个问题还有一个奇妙的解法，工夫复杂度只须要 O(N)，不过该解法比较复杂，我集体认为没必要把握。该算法的名字叫 Manacher’s Algorithm（马拉车算法），有趣味的读者能够自行搜寻一下。
