Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Strings Interleaving

Explore dynamic programming strategies to solve the strings interleaving problem. Understand how to apply brute force, memoization, and tabular methods to efficiently determine if one string is an interleaving of two others. Gain insights into the time and space complexities of each approach.

We'll cover the following...

Solution #1: Brute force

Java
class Interleaving {
 public static boolean findSIRecursive(String m, String n, String p, int mIndex, int nIndex, int pIndex) {
  // if we have reached the end of the all the Strings
  if (mIndex == m.length() && nIndex == n.length() && pIndex == p.length())
   return true;
  // if we have reached the end of 'p' but 'm' or 'n' still has some characters left
  if (pIndex == p.length())
   return false;
  boolean b1 = false, b2 = false;
  if (mIndex < m.length() && m.charAt(mIndex) == p.charAt(pIndex))
   b1 = findSIRecursive(m, n, p, mIndex + 1, nIndex, pIndex + 1);
  if (nIndex < n.length() && n.charAt(nIndex) == p.charAt(pIndex))
   b2 = findSIRecursive(m, n, p, mIndex, nIndex + 1, pIndex + 1);
  return b1 || b2;
 }
 public static Object findSI(String m, String n, String p) {
  return findSIRecursive(m, n, p, 0, 0, 0);
 }
 public static void main(String args[]) {
  System.out.println(findSI("abd", "cef", "adcbef"));
  System.out.println(findSI("abc", "def", "abdccf"));
  System.out.println(findSI("abcdef", "mnop", "mnaobcdepf"));
 }
};

Explanation

The problem follows the longest common subsequence pattern.

A basic brute-force solution is 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.

Time complexity

The time complexity of the above algorithm is exponential O(2m+n)O(2^{m+n}) ...