Strings Interleave Problem

You are given three strings: a, b and i. Write a function that checks whether i is an interleaving of a and b.

String i is said to be interleaving string a and b, if:

len(i) = len(a) + len(b).

i only contains characters present in a or b.

i contains all characters of a. From a, any character a[index] should be added exactly once in i.

i contains all characters of b. From b, any character b[index] should be added exactly once in i.

Order of all characters in individual strings (a and b) is preserved.

‍‍

Example One

Input:

a = “123”

b = “456”

i = “123456”

Output: True

‍

‍Example Two

Input:

a = “AAB”

b = “AAC”

i = “AAAABC”

Output: True

‍

‍Example Three

Input:

a = “AAB”

b = “AAC”

i = “AAABAC”

Output: True

‍Notes

Input Parameters: You will be given three strings a, b and i.

Strings can contain:

Small alphabets – a-z

Large alphabets – A-Z

Numbers – 0-9

Output: Return a boolean if i is an interleaving of a and b.

‍

‍Constraints:

● 0

● 0

‍

Solution

Brute force recursive solution

First character in i should match first character in a or first character in b.

* If it matches first character in a, try matching second character in i with second character in a or first character in b

* If it matches first character in b, try matching second character in i with second character in b or first character in a

* If it matches none of them, terminate with a false

Hence, keep recursing for the rest of the strings. This is an exponential solution, O(2^(len(a)+len(b))) as you can either pick a character from a or a character from b.

‍

Optimal Solution

Convention: str[0 : x] = first x chars of str.

We can say that i[0 : (a_i + b_i)] is an interleaving of a[0 : a_i] and b[0 : b_i], if at least one of the below two is true:

1) – i[0 : (a_i + b_i – 1)] should be an interleaving of a[0 : (a_i – 1)] and b[0 : b_i]

and

– a[ai – 1] == i[ai + bi – 1].

or

2) – i[0 : (a_i + b_i – 1)] should be an interleaving of a[0 : a_i] and b[0 : (b_i – 1)]

and

– b[bi – 1] == i[ai + bi – 1].

‍

We can use DP to keep track of the already calculated values. Have a look at the solution for more details.

Space Complexity:

O(len(a) * len(b))

Time Complexity:

O(len(a) * len(b))

// -------- START --------


bool doStringsInterleave(string a, string b, string i) {
    if (a.length() + b.length() != i.length()){
        return false;
    }
    
    /*
    Convention: str[0 : x] = first x chars of str.
    
    dp[a_i][b_i] =  True if i[0 : (a_i + b_i)] is an interleaving
                    of a[0 : a_i] and b[0 : b_i], else False.
    */
    bool dp[a.length() + 1][b.length() + 1];
    
    for (int ai = 0; ai <= a.length();="" ai++){=""  =""  for="" (int="" bi="0;" <="b.length();" bi++){="" *=""  to="" dp[a_i][b_i]="" be="" true,="" at="" least="" one="" of="" the="" below="" two="" should="" true:=""  1)="" i[0="" :="" (a_i="" +="" b_i="" -="" 1)]="" an="" interleaving=""  of="" a[0="" and="" b[0="" b_i]=""  and="" a[ai="" 1]="=" i[ai="" 1].=""  2)="" a_i]="" (b_i="" b[bi=""  *="" keeps="" track="" above="" mentioned="" #1=""  bool="" dp_ai_min_1_bi="false;" #2="" dp_ai_bi_min_1="false;"  if="" (ai=""> 0){
                dp_ai_min_1_bi = dp[ai - 1][bi] && 
                                 (a[ai - 1] == i[ai + bi - 1]);
            }
            if (bi > 0){
                dp_ai_bi_min_1 = dp[ai][bi - 1] && 
                                 (b[bi - 1] == i[ai + bi - 1]);
            }
            
            // dp[0][0] = Will be true because empty string is an interleaving
            // of two empty strings.
            dp[ai][bi] = (ai == 0 && bi == 0) || 
                         dp_ai_min_1_bi || 
                         dp_ai_bi_min_1;
        }
    }
    
    return dp[a.length()][b.length()];
}


// -------- END --------