classSolution { public: string longestPalindrome(string s){ int n = s.size(); if (n <= 1) { return s; } // 初始dp数组，[i][j]代表下标i到j是回文串 vector<vector<bool>> dp(n, vector<bool>(n, false)); // 一个字符的时候肯定是true for (int i = 0; i < n; i++) { dp[i][i] = true; } // 记录结果字符的起始位置 int maxLength = 1; int begin = 0; // 需要先遍历列j在遍历行i for (int j = 0; j < n; j++) { // i大于j的情况不合法 for (int i = 0; i < j; i++) { // 两个字符相等是回文 if (j == i + 1 && s[i] == s[j]) { dp[i][j] = true; } // 依赖于右上角，注意i+1不能超过j-1 elseif (i + 1 <= j - 1 && dp[i + 1][j - 1] == true && s[i] == s[j]) { dp[i][j] = true; } // 当前是回文，更新最大值 if (dp[i][j] == true && maxLength < j - i + 1) { maxLength = j - i + 1; begin = i; } } } return s.substr(begin, maxLength); } };
代码的时间复杂度和空间复杂度都是 O(N^2)。
建议根据代码的遍历顺序画个矩阵，更方便理解。
一维数组
使用一维数组，就可以降低一层空间复杂度。对应的思路也需要改变。
数组中 dp[j] 的值是下标 j 和 j 之前的最大回文子串的起始下标 i；
易得初始值 dp[0] = 0；
举例字符串 aabba 对应的 dp 数组，第一个 a 的最大回文子串起始地址是他自己，也就是 0；第二个 a 之前的最大回文子串是 aa，所以起始地址是 0；第三个 b 之前的最大回文子串是它自己，因为 aab 不构成回文子串；第四个 b 之前的最大回文子串是 bb，起始地址下标是 2；最后一个 a 的最大回文子串是 abba，起始下标是 1。
classSolution { public: string longestPalindrome(string s){ int n = s.size(); if (n <= 1) { return s; } int maxLength = 1; int maxBegin = 0; for (int i = 0; i < n; i++) { int left = i - 1, right = i + 1; // 扩展 int len = 1; int begin = i; while (left >= 0 && right < n) { if (s[left] != s[right]) { break; } // 相同，记录长度和开始下标 len = right - left + 1; begin = left; // 扩展 left--; right++; } // 更新最大长度 if (len > maxLength) { maxLength = len; maxBegin = begin; } } // 返回结果 return s.substr(maxBegin, maxLength); } };
classSolution { // 从left和right开始往左右扩展找回文子串，返回值是起始下标和长度 pair<int, int> findReverseString(const string& s, int left, int right){ // 记录 int len = 1; int begin = left; // 往两边扩展 while (left >= 0 && right < s.size()) { if (s[left] != s[right]) { break; } // 相同，记录长度和开始下标 len = right - left + 1; begin = left; // 扩展 left--; right++; } return {begin, len}; }
public: string longestPalindrome(string s){ int n = s.size(); if (n <= 1) { return s; } int maxLength = 1; int maxBegin = 0; for (int i = 0; i < n; i++) { // 偶数情况 auto [begin, len] = findReverseString(s, i, i + 1); // 奇数情况 auto [begin2, len2] = findReverseString(s, i - 1, i + 1); // 如果奇数的结果更长，更新结果 if (len2 > len) { len = len2; begin = begin2; } // 更新最大值 if (len > maxLength) { maxLength = len; maxBegin = begin; } } // 返回结果 return s.substr(maxBegin, maxLength); } };
爱发电
