字符串交错合并功能Python运行正常C++输出错误问题排查求助

核心问题列表 #

• 输入读取逻辑错误
  你在使用cin >> in和cin >> out读取文件名后，输入缓冲区中残留了换行符，后续第一次调用getline会读取到这个空换行，导致测试用例的读取顺序完全错位，这是你第一个测试用例输出错误的核心原因。
• 全局DP数组未初始化
  你定义了全局的graph[1001][1001]数组，但是每次处理新的测试用例前没有将其重置为全false，多个测试用例运行时，上一次的数组残留值会干扰本次DP计算的结果。
• DP状态赋值不完整
  你只在状态转移条件满足的时候给graph[i][j]赋值，当A[i-1]和B[j-1]都不等于对应C的字符时，没有显式将graph[i][j]设为false，如果有旧的残留值就会得到错误的状态。
• 大写转换逻辑冗余
  你提前把整个A字符串转大写，虽然不直接影响结果，但和Python实现逻辑不一致，存在潜在风险。

修复后完整代码 #

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
#include <cstring>
using namespace std;

bool graph[1001][1001];

bool isInterleaved(string A, string B, string C)
{
    int M = A.size();
    int N = B.size();
    // 每次运行前重置DP数组
    memset(graph, 0, sizeof(graph));
    if(M + N != C.size())
    {
        return false;
    }
    for (int i = 0; i < M + 1; i++) 
    {
        for(int j = 0; j < N + 1; j++) 
        {
            if (i == 0 && j == 0) { 
                graph[i][j] = true; 
            }
            else if(i == 0) 
            {
                graph[i][j] = (B[j-1] == C[j-1]) && graph[i][j-1];
            }
            else if(j == 0)
            {
                graph[i][j] = (A[i-1] == C[i-1]) && graph[i-1][j];
            }
            else if (A[i - 1] == C[i + j - 1] && B[j - 1] != C[i + j - 1])
            {
                graph[i][j] = graph[i-1][j];
            }
            else if (A[i - 1] != C[i + j - 1] && B[j - 1] == C[i + j - 1])
            {
                graph[i][j] = graph[i][j-1];
            }
            else if (A[i - 1] == C[i + j - 1] && B[j - 1] == C[i + j - 1])
            {
                graph[i][j] = (graph[i - 1][j] || graph[i][j - 1]);
            }
            else
            {
                // 两个字符都不匹配，状态为false
                graph[i][j] = false;
            }
        }
    }
    return graph[M][N];
}

string findPath(string A, string B)
{
    string output = "";
    int M = A.size();
    int N = B.size();
    int i = M;
    int j = N;

    while(j > 0)
    {
        if(graph[i][j-1])
        {
            output = B[j - 1] + output;
            j -= 1;
        }
        else
        {
            output = (char)toupper((unsigned char)A[i-1]) + output;
            i -= 1;
        }
    }
    while(i > 0)
    {
        output = (char)toupper((unsigned char)A[i-1]) + output;
        i -= 1;
    }
    return output;
}

int main()
{
    string in;
    string out;
    cout << "Enter the name of input file: ";
    cin >> in;
    cout << "Enter the name of output file: ";
    cin >> out;
    // 吃掉cin留下的换行符
    cin.ignore();

    ifstream myfile;
    myfile.open(in);

    ofstream outfile;
    outfile.open(out);
    string line;
    vector<string> arguments;
    int count = 0;

    while(getline(myfile, line))
    {
        arguments.push_back(line);
        count ++;
        if(count == 3)
        {
            count = 0;
            if(isInterleaved(arguments[0], arguments[1], arguments[2]))
            {
                outfile << findPath(arguments[0], arguments[1]) << "\n";
            }
            else
            {
                outfile << "*** NOT A MERGE ***" << "\n";
            }
            arguments.clear();
        }
    }
    myfile.close();
    outfile.close();
    return 0;
}

修复说明 #

1. 读取文件名后调用cin.ignore()吃掉残留的换行符，避免后续getline读取到空行
2. 每次进入isInterleaved函数时调用memset(graph, 0, sizeof(graph))清空DP数组
3. 补全DP状态转移的所有分支，不匹配时显式设为false
4. 移除提前把整个A转大写的逻辑，和Python保持一致，在回溯的时候单个字符转大写
5. 增加了<cctype>和<cstring>头文件引用，修正toupper的调用方式避免未定义行为

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