题目描述题目来源LeetCode 第 5 题标签字符串、动态规划、中心扩展题目要求给你一个字符串s找到s中最长的回文子串。什么是回文串如果一个字符串正着读和反着读是一样的那么它就是回文串。例如aba、abba都是回文串。提示与约束条件1 s.length 1000s仅由数字和英文字母组成方法一字符串反转 最长公共子串1. 初始思路回文串的特性是“正读反读都一样”。一个直观的想法是将原字符串s反转得到ss然后寻找s和ss的最长公共子串LCS。这个公共子串理论上就是最长回文子串。2. 逻辑漏洞与修正漏洞仅仅寻找公共子串是不够的。例如s abacdfgdcaba反转后ss abacdfgdcaba两者的最长公共子串是abacd但它并不是回文。修正必须验证找到的公共子串在原字符串中的索引与反转字符串中的索引是否满足对称关系。即若s中起始索引为iss中起始索引为j匹配长度为len则必须满足i j len s.size()才能保证它是真正的回文。3. 代码实现class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ; string ss s; reverse(ss.begin(), ss.end()); string ans ; for (int i 0; i s.size(); i) { for (int j 0; j ss.size(); j) { int len 0; while (i len s.size() j len ss.size() s[i len] ss[j len]) { len; } // 核心修正验证索引对称性 if (len ans.size() i j len s.size()) { ans s.substr(i, len); } } } return ans; } };复杂度分析时间复杂度O(n3)。双层循环枚举起点为 O(n2)内部while匹配最坏情况为 O(n)。空间复杂度O(n)。需要存储反转字符串s。方法二中心扩展法最优解法1. 思路转变放弃“反转匹配”的间接思路回归回文的本质对称性。回文串一定有一个“中心”从这个中心向两边扩展两边的字符必定相等。中心可能有两种情况奇数长度中心是一个字符如aba中心是b。偶数长度中心是两个字符之间的空隙如abba中心在两个b之间。我们只需遍历字符串的每一个位置将其作为中心向两边扩展记录最长的回文即可。2. 代码实现class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ; int start 0, maxLen 1; for (int i 0; i s.size(); i) { // 奇数长度回文扩展 int len1 expandAroundCenter(s, i, i); // 偶数长度回文扩展 int len2 expandAroundCenter(s, i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substr(start, maxLen); } private: int expandAroundCenter(const string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } return right - left - 1; } };复杂度分析时间复杂度O(n2)。共有 2n−1个中心每个中心最多扩展 O(n) 次。空间复杂度O(1)。只需常数级别的额外空间无需存储反转字符串。总结与对比方法核心关键词时间复杂度空间复杂度反转匹配法反转、公共子串、索引验证O(n3)O(n)中心扩展法对称性、奇偶中心、双指针扩展O(n2)O(1)