Algorithms for Coding Interviews in Java/

...

/

Solution: Strings Interleaving

Solution: Strings Interleaving

Let's analyze the different ways to solve the string interleaving challenge.

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}) ...