题目分析
题目链接：
搜索最佳结果的一个一般思想：先想象这个最佳结果必定具有什么样的特征，然后我们通过这些特征来查找，不断找出很多“候选最佳结果”，最后从这些候选结果中选拔出最佳的结果。
很容易想到，每个回文都有一个“中心”，当回文字符数为基数时，中间的那个字符就是回文中心；但是当回文的字符数为偶数时，回文的中心是最中间的那两个字符，且这两个字符相同。
因此要找到回文，我们要先找到“中心”。对任意一个字符或者相同的两个连续字符，我们都可以假设它为回文的“中心”，向它的左右两边扩展出尽可能长的回文。对于每种假设，我们都能得到一个回文，而最长回文必定由其中的某个假设中得到！
因此解题的思路就清晰了：- 枚举所有假设，求出对应的假设结果（扩展出一段回文）
- 看看哪个假设的结果长度最大。
前一步是“根据结果应有的特征来搜索候选最佳结果”，后一步是“从所有的候选最佳中选拔出真正的最佳结果”。
代码实现
class Solution {public: // 效果：根据输入的中心，向两边扩展出回文 // 输入：left指向中心的左端，right指向中心的右端 void expand(const string &str, int &left, int &right) { while (left > 0 && right < str.length()-1 && str[left-1] == str[right+1]) { --left; ++right; } } string longestPalindrome(string s) { int stringLen = s.length(), maxLeft = 0, maxLen = 0, left = 0, right = 0; if (stringLen <= 1) return s; for (int i = 0; i < stringLen; i++) { if ((stringLen - i)*2-1 <= maxLen) break; // 提前结束的条件，后面不可能再出现更长的回文 // 如果i是【最佳结果】的中心左端点，那么中心右端点要么是i，要么是i+1（此时中心两字符必定相等） // 这里我们利用了【结果应有的特征】来搜索候选最佳结果 left = right = i; expand(s, left, right); if (right-left+1 > maxLen) { maxLeft = left; maxLen = right-left+1; } left = i; right = i+1; if (s[left] == s[right]) { expand(s, left, right); if (right-left+1 > maxLen) { maxLeft = left; maxLen = right-left+1; } } } return s.substr(maxLeft, maxLen); }}; 实际上，我们还可以更好地利用【最佳结果】假设，得到更强的筛选条件，从而减少“候选最佳结果”的数量，进而减少搜索时间。
class Solution {public: // 效果：根据输入的中心，向两边扩展出回文 // 输入：left指向中心的左端，right指向中心的右端 void expand(const string &str, int &left, int &right) { while (left > 0 && right < str.length()-1 && str[left-1] == str[right+1]) { --left; ++right; } } string longestPalindrome(string s) { int stringLen = s.length(), maxLeft = 0, maxLen = 0, left = 0, right = 0; if (stringLen <= 1) return s; for (int i = 0; i < stringLen;) { if ((stringLen - i)*2-1 <= maxLen) break; // 提前结束的条件，后面不可能再出现更长的回文 // 我们还可以这样定义回文的中心：由1个或多个相同字符组成、位置处于回文正中心。比如abccccba中cccc就是中心。 // 如果i是【最佳结果】的中心左端点，那么只要右边出现相同字符，我们就不断右移right，这样得到回文的中心 // 这里我们利用了【结果应有的特征】来搜索候选最佳结果，利用这种特征来搜索更加简洁快速 left = right = i; while (right+1 < stringLen && s[right+1] == s[right]) right++; // 根据新的回文中心的定义，对于abccccba，回文中心的left只能是最左边的c，而不能是第二个c // 因此我们没必要再去假设第二个c是回文中心的left，从而减少了假设的数量和搜索的时间 i = right+1; expand(s, left, right); if (right-left+1 > maxLen) { maxLeft = left; maxLen = right-left+1; } } return s.substr(maxLeft, maxLen); }}; 时间复杂度：O(n^2)，其中n为输入字符串的最大长度。