Brute-force, Recursion

Approach:

To solve this problem, let us solve a smaller problem first. Let’s assume that the length of the string A and B is one and the length of the string C is two. Now to che...read more

Dynamic Programming with memoization

Approach:

 

In the previous approach, the algorithm recursively calculates and compares every possible A and B character with C, which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems. To reiterate, memoization is when we store the results of all previously solved subproblems and return whether C is formed by interleaving A and B or not, from the dp[i][j] if we encounter the problem that has already been solved.

Since there are three states those are changing in the recursive function, but the change in the string C is just a result of a change in string A and string B, so we use the 2-dimensional array dp[][] to store all the subproblems where dp[i][j] will store whether C is formed by interleaving A from 0 to i th character and B from 0 to j th character or not.

 

Steps:

 

1. Create a dp array of size (N+1 * M+1) where N and M are lengths of A and B respectively. Initialize dp table to -1 initially.
2. Then we create a recursive function let’s say isInterleavingUtil and pass A, B, C, n1, n2, n3 and the dp array as arguments, where n1,n2, and n3 are the length of A, B, and C.

bool isInterleaveUtil( A, B, C, n1, n2, n3, dp):

1. If all the strings become empty i.e n1,n2.and n3 become 0, then simply return true.
2. If the length of C is not equal to (length of A + length of B),i.e  n1+n2 != n3 then we simply return false.
3. If we already solve the same subproblem for the remaining of strings A, B and C i.e. dp[n1][n2] != -1, then return dp[n1][n2].
4. If the last character of both A and B matches with the last character of C, then we check for both the cases i.e. retreating A by one character and B by one character i.e call isInterleaveUtil(A, B, C, n1-1, n2, n3-1, dp) and isInterleaveUtil(A, B, C, n1, n2-1, n3-1, dp), and store the result of both functions in dp[n1][n2], and return true, if either of them returns true.
5. If the last character of C matches with the last character of A, but not with the last character of B, we move one character back in A and check recursively. I.e. call  isInterleaveUtil(A, B, C, n1-1, n2, n3-1, dp), then store the result of function in dp[n1][n2]
6. If the last character of C matches with the last character of B, but not with the last character of A, we move one character back in B and check recursively. I.e. call  isInterleaveUtil(A, B, C, n1, n2-1, n3-1, dp), then store the result of function in dp[n1][n2].
7. If the last character of C matches neither with the last character of A nor with the last character of B, then we simply return false.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

 

In the worst case, extra space is required to create the dp array of N*M, i.e. O(N*M) and the recursion stack. Hence, the overall complexity will be O(N*M). 

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the length of the string A and M is the length of string B.

 

In the worst case, for every pair of characters in A and B, it is being computed only once.

So the overall time complexity will be O(N*M).

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M). 
    Space Complexity: O(N * M).

    Where N is the length of the string a and M is the length of string b.
*/

#include 
#include 

bool isInterleaveUtil(string a, string b, string c, int n1, int n2, int n3, vector> &dp){

    // If all the strings become empty, then return true.
    if(n1 == 0 && n2 == 0 && n3 == 0) {
        return true;
    }

    // If the length of "c" is not equal to the sum of the length of "a" and "b", then return false.
    if(n1 + n2 != n3) {
        return false;
    }

    if(dp[n1][n2] != -1) {
        return dp[n1][n2];
    }
  
    if(n1 > 0 && n2 > 0 && n3 > 0 && a[n1 - 1] == c[n3 - 1] && b[n2 - 1] == c[n3 - 1]){
        return dp[n1][n2] = (isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp) || isInterleaveUtil(a, b, c, n1, n2 - 1, n3 - 1, dp));
    }

    else if(n1 > 0 && n3 > 0 && a[n1 - 1] == c[n3 - 1]){
        return dp[n1][n2] = isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp);
    }

    else if(n2 > 0 && n3 > 0 && b[n2 - 1] == c[n3 - 1]){
        return dp[n1][n2] = isInterleaveUtil(a, b, c, n1, n2 - 1, n3 - 1, dp);
    }

    // If the last character of "c" matches neither with the last character of "a" nor with the last character of "b", then we simply return false.
    else{
        return dp[n1][n2] = false;
    }
}

bool isInterleave(string a, string b, string c){

    int n1 = a.length(), n2 = b.length(), n3 = c.length();

    // Create a dp array of size (n1+1)*(n2+1) and initialise it to -1.
    vector> dp(n1 + 1, vector (n2 + 1, -1));

    // Call the util function passing each string along with their lengths as arguments.
    return isInterleaveUtil(a, b, c, n1, n2, n3, dp);
}

Python (3.5)

'''
    Time Complexity: O(N * M). 
    Space Complexity: O(N * M) .
    
    Where N is the length of the string a and M is the length of string b.

'''

def isInterleaveUtil(a, b, c, n1, n2, n3, dp):

    # If all the strings become empty, then return true.
    if n1 == 0 and n2 == 0 and n3 == 0 :
        return True

    # If the length of "c" is not equal to the sum of the length of "a" and "b", then return false.
    if n1 + n2 != n3:
        return False

    if dp[n1][n2] != -1:
        return dp[n1][n2]
  
    if n1 > 0 and n2 > 0 and n3 > 0 and a[n1 - 1] == c[n3 - 1] and b[n2 - 1] == c[n3 - 1]:

        dp[n1][n2] = ((isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp)) or (isInterleaveUtil(a, b, c, n1, n2-1, n3-1, dp)))

        return dp[n1][n2]

    elif n1 > 0 and n3 > 0 and a[n1 - 1] == c[n3 - 1]:

        dp[n1][n2] = isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp)

        return dp[n1][n2]

    elif n2 > 0 and n3 > 0 and b[n2 - 1] == c[n3 - 1]:

        dp[n1][n2] = isInterleaveUtil(a, b, c, n1, n2 - 1, n3 - 1, dp)

        return dp[n1][n2]

    # If the last character of "c" matches neither with the last character of "a" nor with the last character of "b", then we simply return false.
    else:
        dp[n1][n2] = False
        return dp[n1][n2]

def isInterleave(a, b, c):

    # Create a dp list and initialise it to -1.
    dp=[[-1 for i in range(len(b) + 1)] for j in range(len(a) + 1)]

    # Call the util function passing each string along with their lengths as arguments.
    return isInterleaveUtil(a, b, c, len(a), len(b), len(c), dp)

Java (SE 1.8)

/*
    Time Complexity: O(N * M). 
    Space Complexity: O(N * M).

    Where N is the length of the string a and M is the length of string b.
*/

import java.util.ArrayList;

public class Solution {
	private static int isInterleaveUtil(String a, String b, String c, int n1, int n2, int n3,
			ArrayList> dp) {

		// If all the Strings become empty, then return true.
		if (n1 == 0 && n2 == 0 && n3 == 0) {
			return 1;
		}

		// If the length of "c" is not equal to the sum of the length of "a" and "b",
		// then return false.
		if (n1 + n2 != n3) {
			return 0;
		}

		// If the length of "c" is not equal to the sum of the length of "a" and "b",
		// then return false.
		if (n1 + n2 != n3) {
			return 0;
		}

		if (dp.get(n1).get(n2) != -1) {
			return dp.get(n1).get(n2);
		}

		if (n1 > 0 && n2 > 0 && n3 > 0 && a.charAt(n1 - 1) == c.charAt(n3 - 1)
				&& b.charAt(n2 - 1) == c.charAt(n3 - 1)) {
			int ans = isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp)
					| isInterleaveUtil(a, b, c, n1, n2 - 1, n3 - 1, dp);

			// Store the value in the "dp"
			dp.get(n1).set(n2, ans);

			return ans;
		} else if (n1 > 0 && n3 > 0 && a.charAt(n1 - 1) == c.charAt(n3 - 1)) {
			int ans = isInterleaveUtil(a, b, c, n1 - 1, n2, n3 - 1, dp);

			// Store the value in the "dp"
			dp.get(n1).set(n2, ans);

			return ans;
		} else if (n2 > 0 && n3 > 0 && b.charAt(n2 - 1) == c.charAt(n3 - 1)) {
			int ans = isInterleaveUtil(a, b, c, n1, n2 - 1, n3 - 1, dp);

			// Store the value in the "dp"
			dp.get(n1).set(n2, ans);

			return ans;
		} else {
			// If the last character of "c" matches neither with the last character of "a"
			// nor with the last character of "b", then we simply return false.
			dp.get(n1).set(n2, 0);

			return 0;
		}
	}

	public static boolean isInterleave(String a, String b, String c) {

		int n1 = a.length(), n2 = b.length(), n3 = c.length();

		// Create a dp array of size (n1+1)*(n2+1) and initialise it to -1.
		ArrayList> dp = new ArrayList>();
		for (int i = 0; i <= n1; i++) {
			dp.add(new ArrayList());
			for (int j = 0; j <= n2; j++) {
				dp.get(i).add(-1);
			}
		}

		// Call the util function passing each String along with their lengths as
		// arguments.
		int ans = isInterleaveUtil(a, b, c, n1, n2, n3, dp);

		return (ans == 1);
	}
}

Bottom-up DP

Approach:

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. In this, we use the recurrence relation of memoization approach as dp[i][j] = (dp[i...read more

1D DP

Approach:

The space complexity for the last two approaches is O(N*M), however, it can be improved further to O(min(M,N)), if we use 1D dp array. The approach is the same as the previous approach ...read more