DEV Community

Discussion on: Solution: Interleaving String

View post
Collapse
 
mellen profile image
Matt Ellen • • Edited

I think I have an O(N) solution, where N is the length of s3.

function isInterleaved(s1, s2, s3)
{
  let result = true;
  let currentIndex = 0;
  let last = s1;
  let other = s2;
  let lasti = 0
  let otheri = 0;
  while(currentIndex < s3.length - 1)
  {
      if(last[lasti] == s3[currentIndex])
      {
        lasti++;
        currentIndex++;
      }
      else if(other[otheri] == s3[currentIndex])
      {
        otheri++;
        let t = other;
        other = last;
        last = t;
        t = otheri;
        otheri = lasti;
        lasti = t;
        currentIndex++;
      }
      else
      {
        result = false;
        break;
      }
  }
  return result;
}
Enter fullscreen mode Exit fullscreen mode

I might be missing corner cases, or have misunderstood the task 😁

Collapse
 
seanpgallivan profile image
seanpgallivan •

Unfortunately, this code always picks from last if the current letter matches s3. But what if the current letter of both last and other match? You would need to try both options to see if either works.

Consider s1 = "ba", s2 = "bc", s3 = "bcba". Your solution would pick the "b" from s1 but then would return a false because its only options would be the "a" from s1 or the "b" from s2 to match the "c" from s3. But clearly, we can take the entire "bc" from s2 and then the entire "ba" from s1 to match s3, so the answer should be true.

We could use a recursive or stack approach at this point to try the multiple branches, but then we'd start overlapping cases and redoing the same subproblems, which will take too long. This is the issue that dynamic programming helps to solve, by storing the results of these subproblems in a way that allows them to be accessed again, rather than resolving.

Collapse
 
mellen profile image
Matt Ellen •

Ah! Thanks for insight.