Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Strings Interleaving

Explore multiple methods to determine if one string is an interleaving of two others. Understand the drawbacks of brute force, apply recursive and memoization strategies, and master the tabular dynamic programming solution to improve efficiency.

We'll cover the following...

Solution #1: Brute Force (Not Accurate)

C++
#include <iostream>
#include <string>
using namespace std;
bool isInterleaved(string str1, string str2, string strToCheck) {
  
  int i=0, j=0, k=0;
  
  if(str1.length() + str2.length() != strToCheck.length()){
   return false;
  }
  
  while(k < strToCheck.length()){
   
   if( i < str1.length() && str1[i] == strToCheck[k]){
    i++;
   
   }else if(j < str2.length() && str2[j] == strToCheck[k]){
    j++;
   
   }else{
    return false;
   }
   
   k++;
  }
  
  if(!(i == str1.length() && j == str2.length() && k == strToCheck.length())){
   return false;
  }
  
  return true;
 }
int main() {
    cout << isInterleaved("ABC", "ACD", "ACDABC") << endl;
}

This solution works by comparing the possibly interleaved string to the given strings character by character.

Here’s the exact algorithm:

  1. Check whether the size of strToCheck is equal to str1 length + string2 length. If No, then string is not interleaved and return.

  2. If the size is equal then iterate through the given interleaved string (strToCheck) and compare each character against str1 and str2. If it matches with either, then increment the pointers of the relevant string. So if the match happened in str1, then increment i.

  3. If at any point, a character in the interleaved string is not matching with any of the given 2 strings then the given string (strToCheck) is not interleaved.

Caveat with this solution is that it will NOT work when the given strings have duplicate characters in them! This is because the algorithm will not be able to tell which character in the interleaved string belongs to which given string and hence will not be able to recognize the order!

To take care of this problem, we can use a recursive solution. Check out solution #2.

Time Complexity

The time complexity of this code is in O(m+n)O(m+n) ...