check whether a string C is an interleaving of A and B

Question

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.

For example:

• 'hotdog' is an interleaving of 'hot' and 'dog' (easy)
• 'superb' is an interleaving of 'up' and 'serb'
• 'heartache' is an interleaving of 'ear' and 'ache'
• 'chat' is an interleaving of 'hat' and 'cat'
• 'cheaters' is not an interleaving of 'chat' and 'seer', because while it contains all the letters from each, the letters from 'seer' do not appear in order

I find some solutions in net but below is my approach can somebody tell me am i missing something or my algo will work? thanks.

My Algo:

1. Traverse through a and c. While traversal we calculate two things first: whether the char is present or not and save the index i.e. f where the char is found. And as soon as we find the char we should put some special char in that place, so that we will not consider this char further.
2. For the next char in a search in the c from the index where you have found the previous char i.e. f. if we don't find than return.
3. Same you do for b as well.
4. If after doing the above step if we find false than repeat for first b than a and return the result.

e.g.

a = xxy, b = xxz and c = xxzxxxy

start with a:

1. for x in a, c = 0xzxxxy (i am putting 0 as special char)
2. for x in a, start from the index 0 onwards(because we have found the previous char at 0)c = 00zxxxy.
3. for y in a, c = 00zxxx0
4. for x in b, c = 00z0xx0
5. for x in b, c = 00z00x0
6. for z in b, we could not find z after the index 4 which was the index where we found the previous char for b.

as starting with a returns false so we will start with b now.

So start with b:

1. for x in b, c = 0xzxxxy
2. for x in b, c = 00zxxxy
3. for z in b, c = 000xxxy
4. for x in a, c = 0000xxy
5. for x in a, c = 00000xy
6. for y in a, c = 00000x0

hence true i.e.c is the interleaved string of a and b.

Answer 1

Your solution represents a greedy algorithm with a slight modification, because it counts a character in C as belonging to A on the first pass (or to B on the second pass) as soon as it finds a match. This will break for the following strings:

A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz

The firs pass that counts a matching character as a member of A will turn C into

00zxx0000xxz

The second pass that counts a matching character as a member of B will turn C into

00000yxxyxx0

Here is a simple Java implementation of a memoized solution:

private static boolean checkOverlap(String a, String b, String c) {
    Boolean[][][] memoize = new Boolean[a.length()+1][b.length()+1][c.length()+1];
    return checkOverlap(a, b, c, 0, 0, 0, memoize);
}
private static boolean checkOverlap(
    String a
,   String b
,   String c
,   int pa
,   int pb
,   int pc
,   Boolean[][][] memoize
) {
    Boolean res = memoize[pa][pb][pc];
    if (res != null) {
        return (boolean)res;
    }
    if (pa == a.length() && pb == b.length() && pc == c.length()) {
        res = true;
    } else if (pc == c.length()) {
        res = false;
    } else {
        res = false;
        if (pa != a.length() && c.charAt(pc) == a.charAt(pa) && checkOverlap(a, b, c, pa+1, pb, pc+1, memoize)) {
            res = true;
        } else if (pb != b.length() && c.charAt(pc) == b.charAt(pb) && checkOverlap(a, b, c, pa, pb+1, pc+1, memoize)) {
            res = true;
        }
    }
    return (memoize[pa][pb][pc] = res);
}

Demo on ideone.