最长回文子串代码异常排查：输入"aaaaa"仅返回长度3的结果

我在解决最长回文子串问题时，输入"aaaaa"后代码返回的最长回文子串长度只有3，不符合预期。我的思路是维护一个dp数组：

• 长度为1的子串设为1（表示是回文）
• 长度为2且两端字符相同的子串设为1
• 其余情况仅当s[i]==s[j]且dp[i+1][j-1]==1时，才将dp[i][j]设为1

我的代码如下：

class Solution {
    public:
        string longestPalindrome(string s) {
            int n = s.size();
            int dp[n][n];
            int fini=0,finj=0;
            for(int i=0; i<s.size(); i++)
                for(int j=0; j<s.size(); j++){
                    if(i==j)
                            dp[i][j]=1;
                    else
                        dp[i][j]=0;
                }
            for(int i=0; i<s.size()-1; i++){
                    if(s[i]==s[i+1]){
                        dp[i][i+1]=1;
                        fini = i;
                        finj = i+1;
                        
                    }
            }
            //cout<<dp[1][6];
            cout<<fini<<finj<<endl;
            for(int i=0; i<s.size()-1; i++){
                for(int j=i+1; j<s.size(); j++){
                    cout<<"dp"<<" "<<i<<" "<<j<<' '<<dp[i][j]<<" "<<dp[i+1][j-1]<<endl;
                    if(s[i]==s[j] && dp[i+1][j-1]){
                            dp[i][j]=1;
                            if(abs(j-i+1)>abs(finj-fini+1)){
                                fini=i;
                                finj=j;
                            }
                                    cout<<fini<<" "<<finj<<endl;
    
                        }
                    
                    }     
                                
                }
            
            return s.substr(fini, finj-fini+1);
        }
    };

问题根源 #

你的dp数组遍历顺序错误。当前代码按i从小到大、j从i+1到末尾的顺序遍历，会导致处理长串时，内部依赖的短串状态还没被计算。比如处理i=0,j=4（整个"aaaaa"）时，dp[1][3]还没被赋值为1——因为i=1,j=3的遍历要等到i=0的循环结束后才执行，此时判断条件不成立，dp[0][4]无法被设为1，自然无法更新最长回文的范围。

修正方案 #

正确的遍历顺序应该是按子串长度从小到大处理：先处理长度1，再长度2，接着从长度3到n依次处理。这样当计算长度为l的子串时，所有长度为l-2的子串（即dp[i+1][j-1]对应的子串）已经被正确计算过。

修正后的代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n == 0) return "";
        bool dp[n][n];
        memset(dp, 0, sizeof(dp));
        int fini = 0, finj = 0;

        // 初始化长度为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;
                fini = i;
                finj = i+1;
            }
        }

        // 处理长度>=3的子串，l为子串长度
        for (int l = 3; l <= n; ++l) {
            for (int i = 0; i <= n - l; ++i) {
                int j = i + l - 1; // 子串右端点
                if (s[i] == s[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                    // 更新最长回文范围
                    if (j - i + 1 > finj - fini + 1) {
                        fini = i;
                        finj = j;
                    }
                }
            }
        }

        return s.substr(fini, finj - fini + 1);
    }
};

额外优化点 #

1. 把int类型的dp数组改成bool类型，更贴合回文的判断逻辑，同时用memset初始化避免栈数组的未初始化垃圾值问题。
2. 增加了n=0的边界处理，避免空字符串输入时出错。

内容的提问来源于stack exchange，提问作者Somyadeep Shrivastava