Solution: Strings Interleaving

Grokking Dynamic Programming Patterns for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Strings Interleaving

Table of Contents

Contents are not accessible

Problem Statement

Given three strings 'm', 'n', and 'p', write a method to find out if 'p' has been formed by interleaving 'm' and 'n'. 'p' would be considered interleaving 'm' and 'n' if it contains all the letters from 'm' and 'n' and the order of letters is preserved too.

Example 1:

Input: m="abd", n="cef", p="abcdef"
Output: true
Explanation: 'p' contains all the letters from 'm' and 'n' and preserves their order too.

Example 2:

Input: m="abd", n="cef", p="adcbef"
Output: false
Explanation: 'p' contains all the letters from 'm' and 'n' but does not preserve the order.

Example 3:

Input: m="abc", n="def", p="abdccf"
Output: false
Explanation: 'p' does not contain all the letters from 'm' and 'n'.

Example 4:

Input: m="abcdef", n="mnop", p="mnaobcdepf"
Output: true
Explanation: 'p' contains all the letters from 'm' and 'n' and preserves their order too.

Constraints:

0 <= m.length, n.length <= 100
0 <= p.length <= 200
m, n, and p consist of lowercase English letters.

Basic Solution

The problem follows the "Longest Common Subsequence" (LCS) pattern and has some similarities with "Subsequence Pattern Matching".

A basic brute-force solution could be to try matching 'm' and 'n' with 'p' one letter at a time. Let's assume mIndex, nIndex, and pIndex represent the current indexes of 'm', 'n', and 'p' strings respectively. Therefore, we have two options at any step:

If the letter at mIndex matches with the letter at pIndex, we can recursively match for the remaining lengths of 'm' and 'p'.
If the letter at nIndex matches with the letter at 'pIndex', we can recursively match for the remaining lengths of 'n' and 'p'.

Code

Here is the code:

Python3

. . . .

The time complexity of the above algorithm is exponential $O(2^{m+n})$ , where 'm' and 'n' are the lengths of the two interleaving strings. The space complexity is $O(m+n)$ , the value that is used to store the recursion stack.

Top-down Dynamic Programming with Memoization

This problem can have overlapping subproblems only when there are some common letters between 'm' and 'n' at the same index. Because whenever we hit such a scenario, we get an option to match with any one of them.

The three changing values in our recursive function are the three indexes mIndex, nIndex, and pIndex. Therefore, we can store the results of all the subproblems in a three-dimensional array. Alternately, we can use a hash-table whose key would be a string (mIndex + "|" + nIndex + "|" + pIndex).

Code

Here is the code:

Python3

. . . .

Bottom-up Dynamic Programming

Since we want to completely match 'm' and ‘n’ (the two interleaving strings) with 'p', we can use a two-dimensional array to store our results. The lengths of 'm' and 'n' will define the dimensions of the result array.

As mentioned above, we will be tracking separate indexes for 'm', 'n' and 'p', so we will have the following options for every value of mIndex, nIndex, and pIndex:

If the character m[mIndex] matches the character p[pIndex], we will take the matching result up to mIndex-1 and nIndex.
If the character n[nIndex] matches the character p[pIndex], we will take the matching result up to mIndex and nIndex-1.

String 'p' will be interleaving strings 'm' and 'n' if any of the above two options is true. This is also required as there could be some common letters between 'm' and 'n'.

So our recursive formula would look like:

dp[mIndex][nIndex] = false
if m[mIndex] == p[pIndex] 
  dp[mIndex][nIndex] = dp[mIndex-1][nIndex]
if n[nIndex] == p[pIndex] 
 dp[mIndex][nIndex] |= dp[mIndex][nIndex-1]

Let's draw this visually:

Code

Here is the code for our bottom-up dynamic programming approach:

Python3

. . . .

The time and space complexity of the above algorithm is $O(m*n)$ , where 'm' and 'n' are the lengths of the two interleaving strings.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible