Algorithms for Coding Interviews in C++/

...

/

Solution: Strings Interleaving

Solution: Strings Interleaving

Let's analyze the different ways to solve the string interleaving problem

We'll cover the following...

Solution #1: Brute Force (Not Accurate)

Press + to interact
#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) ...