## 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.