Find if a string is interleaved of two other strings | DP-33

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 and only characters of A and B and order of all characters in individual strings is preserved. 

Example: 

Input: strings: "XXXXZY", "XXY", "XXZ"
Output: XXXXZY is interleaved of XXY and XXZ
The string XXXXZY can be made by 
interleaving XXY and XXZ
String:    XXXXZY
String 1:    XX Y
String 2:  XX  Z

Input: strings: "XXY", "YX", "X"
Output: XXY is not interleaved of YX and X
XXY cannot be formed by interleaving YX and X.
The strings that can be formed are YXX and XYX

Method 1: Recursion. 
Approach: A simple solution is discussed here: Check whether a given string is an interleaving of two other given string. 
The simple solution doesn’t work if the strings A and B have some common characters. For example, let the given string be A and the other strings be B and C. Let A = “XXY”, string B = “XXZ” and string C = “XXZXXXY”. Create a recursive function that takes parameters A, B, and C. To handle all cases, two possibilities need to be considered.

1. If the first character of C matches the first character of A, we move one character ahead in A and C and recursively check.
2. If the first character of C matches the first character of B, we move one character ahead in B and C and recursively check.

If any of the above function returns true or A, B and C are empty then return true else return false.
Thanks to Frederic for suggesting this approach.

Complexity Analysis: 

• Time Complexity: O(2^n), where n is the length of the given string. 
• Space Complexity: O(1). 
  The space complexity is constant.

Method 2: Dynamic Programming. 
Approach: The above recursive solution certainly has many overlapping sub-problems. For example, if we consider A = “XXX”, B = “XXX” and C = “XXXXXX” and draw a recursion tree, there will be many overlapping subproblems. Therefore, like any other typical Dynamic Programming problems, we can solve it by creating a table and store results of sub-problems in a bottom-up manner. The top-down approach of the above solution can be modified by adding a Hash Map.

Algorithm: 

1. Create a DP array (matrix) of size M*N, where m is the size of the first string and n is the size of the second string. Initialize the matrix to false.
2. If the sum of sizes of smaller strings is not equal to the size of the larger string then return false and break the array as they cant be the interleaved to form the larger string.
3. Run a nested loop the outer loop from 0 to m and the inner loop from 0 to n. Loop counters are i and j.
4. If the values of i and j are both zeroes then mark dp[i][j] as true. If the value of i is zero and j is non zero and the j-1 character of B is equal to j-1 character of C the assign dp[i][j] as dp[i][j-1] and similarly if j is 0 then match i-1 th character of C and A and if it matches then assign dp[i][j] as dp[i-1][j].
5. Take three characters x, y, z as (i-1)th character of A and (j-1)th character of B and (i + j – 1)th character of C.
6. if x matches with z and y does not match with z then assign dp[i][j] as dp[i-1][j] similarly if x is not equal to z and y is equal to z then assign dp[i][j] as dp[i][j-1]
7. if x is equal to y and y is equal to z then assign dp[i][j] as bitwise OR of dp[i][j-1] and dp[i-1][j].
8. return value of dp[m][n].

Thanks to Abhinav Ramana for suggesting this method of implementation. 

Output: 

XXZXXXY is not interleaved of XXY and XXZ
WZXY is interleaved of XY and WZ
XXY is interleaved of XY and X
XXY is not interleaved of YX and X
XXXXZY is interleaved of XXY and XXZ

See this for more test cases.
Complexity Analysis: 

• Time Complexity: O(M*N). 
  Since a traversal of the DP array is needed, so the time complexity is O(M*N).
• Space Complexity: O(M*N). 
  This is the space required to store the DP array.

https://youtu.be/WBXy-sztEwI 
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above. 

Method 3: Dynamic Programming(Memoization)

Approach: We can make a matrix where rows and columns represent the characters of the string A and B. If C is the interleaved string of A and B then there exists a path from the top left of the Matrix to the bottom right. That is if we can go from index 0,0 to n,m while matching characters of all A and B with C then C is interleaved of A and B.

Let A be “XXY”, B be “XXZ” and C be “XXZXXY” then the path would look something like this:

let us consider one more example, let A be “ABC”, B be “DEF” and C be “ADBECF”, then the path would look something like this:

If there exists a path through which we can reach R, then C is the interleaved strings of A and B.

Algorithm:

1. We will first create a matrix dp to store the path since one path can be explored multiple times, the Matrix index dp[i][j] will store if there exists a path from this index or not.

2. If we are at i’th index of A and j’th index of B and C[i+j] matches both A[i] and B[j] then we explore both the paths that are we will go right and down i.e. we will explore index i+1,j and j+1,i.

3. If C[i+j] only matches with A[i] or B[j] then we will go just down or right respectively that is i+1,j or i,j+1.

XXZXXXY is not interleaved of XXY and XXZ
WZXY is interleaved of XY and WZ
XXY is interleaved of XY and X
XXY is not interleaved of YX and X
XXXXZY is interleaved of XXY and XXZ
DAACSA is interleaved of ACA and DAS

Complexity Analysis:

Time Complexity:  O(m*n).

This is the worst case of time complexity, if the given strings contain no common character matching with C then the time complexity will be O(n+m).
Space Complexity: O(m*n).

This is the space required to store the DP array.

The above method and implementation are contributed by Anirudh Singh.