Combine Two Strings

The question

We are given 3 strings: str1, str2, and str3. Str3 is said to be a shuffle of str1 and str2 if it can be formed by interleaving the characters of str1 and str2 in a way that maintains the left to right ordering of the characters from each string. For example, given str1=”abc” and str2=”def”, str3=”dabecf” is a valid shuffle since it preserves the character ordering of the two strings. So, given these 3 strings write a function that detects whether str3 is a valid shuffle of str1 and str2.

The solution

When I read the question for the first time I though edge cases might make this a little tricky, but it seems like they take care of themselves. What I thought of doing is:

– Set one pointer to the last letter of str1

– Set one pointer to the last letter of str2

– Set one pointer to the last letter of str3

– Grab the letter at str3 and compare it to the letter at str2.

– If they match move str3 and str2 one letter to the left

– If they don’t match then compare str3 to str1

– If they match move str3 and str1 one letter to the left

– If they don’t match then str3 is not a shuffle

– Repeat until there are not more letters on str3

This seems to work fine for all the tests I did and the complexity is O(n), where n is the length of the shuffle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function isShuffle(str1, str2, shuffle) {
  var pointer1 = str1.length - 1;
  var pointer2 = str2.length - 1;
  var shufflePointer = shuffle.length - 1;

  while (shufflePointer >= 0) {
    if (shuffle[shufflePointer] === str2[pointer2]) {
      pointer2--;
    } else if (shuffle[shufflePointer] === str1[pointer1]){
      pointer1--;
    } else {
      return false;
    }

    shufflePointer--;
  }
  return true;
}

function test() {
  if (isShuffle('acc', 'abc', 'abaccc') === true &&
      isShuffle('acc', 'abc', 'baacc') === false) {
    console.log('success');
  }
}

test(); // Prints success

The recommended solution on Arden’s site uses recursion but it doesn’t seem like it is more efficient than my suggested solution so I’ll stick to my version.