寻求最长回文子串算法时间复杂度优化方案（LeetCode TLE问题）

阿华AIGC实验室

2026-5-9

优化「最长回文子串」解法以解决TLE问题

Hi there! 首先欢迎你第一次发帖😊，你的问题描述很清晰，咱们一步步来解决这个超时的问题。

先分析你当前代码的问题

你的代码逻辑是遍历每个起始位置，然后尝试从当前最长长度+1开始截取子串，判断是否是回文。但这里有几个导致超时的关键点：

频繁截取子串：s.substr(curr_pos,i)每次都会生成新的字符串，这不仅有额外的内存开销，还增加了时间成本。
std::equal的实际开销：你猜的没错，std::equal在这里的时间复杂度确实是O(k)（k是子串长度的一半），而且结合外层的两层循环，实际的时间复杂度其实是O(N³)——因为对于每个起始位置，你可能要检查多个子串，每个子串的回文判断又要O(k)时间，这就远超你预期的O(N²)了。
循环内的i=max操作：这个调整虽然想跳过一些短子串，但实际逻辑可能没达到预期效果，反而可能让循环的控制变得混乱。

可行的优化方案

1. 中心扩展法（时间O(N²)，空间O(1)，最容易实现且高效）

回文的特点是可以以某个字符（奇数长度）或两个字符之间的间隙（偶数长度）为中心，向两边扩展，直到无法形成回文为止。这种方法不需要额外的空间，而且避免了频繁的子串生成和拷贝。

2. 动态规划（DP）方案

DP确实可以用来解决这个问题，核心思路是用dp[i][j]表示字符串从索引i到j的子串是否是回文：

当i == j时，dp[i][j] = true（单个字符是回文）
当j - i == 1时，dp[i][j] = (s[i] == s[j])（两个字符相等就是回文）
当j - i > 1时，dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]（两端字符相等，且中间子串是回文）

不过DP的空间复杂度是O(N²)，如果字符串很长，空间开销会比中心扩展法大，但时间复杂度同样是O(N²)。

3. 针对你原代码的直接优化（如果想保留类似思路）

如果你想基于自己的代码修改，最关键的是避免生成子串，直接在原字符串上判断回文，而不是截取后再判断。比如，对于起始位置curr_pos和结束位置end，直接比较s[curr_pos + k]和s[end - k]（k从0到中间位置）。

改进后的代码示例

中心扩展法实现

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() < 2) return s;
        int start = 0, max_len = 1;
        
        // 辅助函数：扩展中心，返回回文的长度
        auto expandAroundCenter = [&](int left, int right) {
            while (left >= 0 && right < s.length() && s[left] == s[right]) {
                left--;
                right++;
            }
            // 退出循环时，left和right已经不满足条件，所以实际长度是right-left-1
            return right - left - 1;
        };
        
        for (int i = 0; i < s.length(); ++i) {
            int len1 = expandAroundCenter(i, i); // 奇数长度中心
            int len2 = expandAroundCenter(i, i+1); // 偶数长度中心
            int curr_len = max(len1, len2);
            
            if (curr_len > max_len) {
                max_len = curr_len;
                // 计算起始位置：i - (curr_len-1)/2
                start = i - (curr_len - 1) / 2;
            }
        }
        
        return s.substr(start, max_len);
    }
};

DP实现（供参考）

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n < 2) return s;
        
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int start = 0, max_len = 1;
        
        // 单个字符都是回文
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }
        
        // 检查长度为2的子串
        for (int i = 0; i < n-1; ++i) {
            if (s[i] == s[i+1]) {
                dp[i][i+1] = true;
                start = i;
                max_len = 2;
            }
        }
        
        // 检查长度>=3的子串
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    start = i;
                    max_len = len;
                }
            }
        }
        
        return s.substr(start, max_len);
    }
};