c++ - 检查一个字符串是否被另外两个字符串交错

Question

我正在调试以下问题。发布详细的问题陈述和编码。我的问题是最后一个 else if (else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])) 是必要的吗？我认为没有必要，因为它总是被 else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j- 1])，或者被覆盖 else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1] )，即前两个if-else检查条件。谢谢。

给定s1、s2、s3，判断s3是否由s1和s2交织而成。

例如， 鉴于: s1 = "aabcc", s2 = "dbbca",

当 s3 = "aadbbcbcac"时，返回 true。 当 s3 = "aadbbbaccc"时，返回 false。

// The main function that returns true if C is
// an interleaving of A and B, otherwise false.
bool isInterleaved(char* A, char* B, char* C)
{
    // Find lengths of the two strings
    int M = strlen(A), N = strlen(B);

    // Let us create a 2D table to store solutions of
    // subproblems.  C[i][j] will be true if C[0..i+j-1]
    // is an interleaving of A[0..i-1] and B[0..j-1].
    bool IL[M+1][N+1];

    memset(IL, 0, sizeof(IL)); // Initialize all values as false.

    // C can be an interleaving of A and B only of sum
    // of lengths of A & B is equal to length of C.
    if ((M+N) != strlen(C))
       return false;

    // Process all characters of A and B
    for (int i=0; i<=M; ++i)
    {
        for (int j=0; j<=N; ++j)
        {
            // two empty strings have an empty string
            // as interleaving
            if (i==0 && j==0)
                IL[i][j] = true;

            // A is empty
            else if (i==0 && B[j-1]==C[j-1])
                IL[i][j] = IL[i][j-1];

            // B is empty
            else if (j==0 && A[i-1]==C[i-1])
                IL[i][j] = IL[i-1][j];

            // Current character of C matches with current character of A,
            // but doesn't match with current character of B
            else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1])
                IL[i][j] = IL[i-1][j];

            // Current character of C matches with current character of B,
            // but doesn't match with current character of A
            else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1])
                IL[i][j] = IL[i][j-1];

            // Current character of C matches with that of both A and B
            else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
                IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;
        }
    }

    return IL[M][N];
}

提前致谢， 林

Answer 1

你确实需要最后的 else if捕捉 C 中的下一个字符与 A 和 B 中的下一个字符匹配的情况。例如，使用 A="aaaa" 运行程序, B="aaaa" , 和 C="aaaaaaaa"看看你是否输入了最后一个 else if堵塞。

另外，你还需要一个final else阻止处理先前条件都不匹配的情况。在这种情况下，您需要设置 IL[i][j]至 false .否则，该函数将错误地返回 true。 .

编辑:即使代码使用了 memset初始化 IL 的所有元素至 0 , 它可能不起作用，因为 ISO C++ does not support可变长度数组 (VLA)。事实上，这就是我 tried the code at cpp.sh 时发生的事情。 .它使用带有标志的 g++-4.9.2 导致它报告 sizeof(IL)成为1尽管g++应该支持 VLA。也许这是一个编译器错误，或者它不支持多维 VLA。无论如何，根本不使用它们可能更安全。