check if one string is interleaved by two other strings

Question

I am debugging the following problem. Post detailed problem statement and the coding. My question is whether the last else if (else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])) is necessary? I think it is not necessary since it is always covered either by else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1]), or covered by else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1]), i.e. previous two if-else check conditions. Thanks.

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return 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];
}

thanks in advance, Lin

I think you do need the last case. For example, what happens when `A="aaaa"`, `B="aaaa"`, and `C="aaaaaaaa"`. — crayzeewulf, Oct 25 '15 at 05:52
Also, there are other problems in your algorithm. For example, I do not see anywhere where you set any element of `IL[][]` to `false`. Your function probably always returns `true`. You probably need a final `else` block where `IL[i][j]` should be set to `false`. — crayzeewulf, Oct 25 '15 at 05:57
@crayzeewulf, thanks for the response, I do not quite catch your ideas. Why in your sample, previous two else-if never already covers and handles well? Thanks. — Lin Ma, Oct 25 '15 at 06:06
@crayzeewulf, thanks for the catch, "You probably need a final else block where IL[i][j] should be set to false". I think I can initialize IL to false at the beginning, the same effect, correct? — Lin Ma, Oct 25 '15 at 06:07
Put a breakpoint or a print in that last `else if` block and see if the program gets there in the example case I mentioned above. As the comments in the code say, the previous two `else if` statements will not catch the condition where a character in C matches characters in both A and B. — crayzeewulf, Oct 25 '15 at 06:12
@crayzeewulf, got what you mean, pretty cool. Do you think I an rewrite the code to be more elegant, saying if (A[i-1]==C[i+j-1] || B[j-1]==C[i+j-1]), then IL[i][j]=(IL[i-1][j] || IL[i][j-1])? I mean using the statement to replace all last 3 else-if. Correct? Thanks. — Lin Ma, Oct 25 '15 at 06:20
I think it is cleaner the way it is. However, I do suggest replacing the use of `char*` with `std::string`. If you want to keep using `char*`, at least declare the parameters `const char*` since you are not modifying them. This way you can call the function with string literals and `const` strings. For example, `isInterleaved("aaa", b, c)`. — crayzeewulf, Oct 25 '15 at 06:25
@crayzeewulf, accepted, thanks for all the help. Thanks. Good weekend. :) — Lin Ma, Oct 25 '15 at 06:25
Done. But don't hesitate to [answer your own questions](http://stackoverflow.com/help/self-answer). It is okay and encouraged. :D — crayzeewulf, Oct 25 '15 at 06:32
No. The condition in the last elseif is mutually excusiuve with the previous two conditions. Also your code relies on VLAs that standard C++ doesn't have, and never set any element to `false`. Perhaps your particular compiler guarantees to initialize `bool` VLAs to false, I can't tell. — n. m. could be an AI, Oct 25 '15 at 06:48
@n.m., which line of my code is VLA? I am confused. Appreciate for pointing out in more details. :) — Lin Ma, Oct 29 '15 at 22:31
`bool IL[M+1][N+1];` This is not standard. Dimensions must be constant expressions. — n. m. could be an AI, Oct 29 '15 at 23:05

score 2 · Accepted Answer · edited May 23 '17 at 11:58

You do need the final else if to catch the cases when the next character in C matches the next character in both A and B. For example, run your program with A="aaaa", B="aaaa", and C="aaaaaaaa" and see if you enter that last else if block.

Additionally, you also need a final else block to handle cases when none of the previous conditions match. In this case, you need to set IL[i][j] to false. Otherwise, the function will incorrectly return true.

Edit: Even though the code uses memset to initialize all elements of IL to 0, it may not work because ISO C++ does not support variable length arrays (VLAs). In fact, this is what happened when I tried the code at cpp.sh. It uses g++-4.9.2 with flags that causes it to report sizeof(IL) to be 1 even though g++ is supposed to support VLAs. Maybe this is a compiler bug or maybe it does not support multidimensional VLAs. In any case, it might be safer to not use them at all.

check if one string is interleaved by two other strings

1 Answers1