LeetCode problem #30 — Substring With Concatenation Of All Words (JavaScript)

In this LeetCode problem, we’re given a string, and a series of words, and asked to find all points in the string where you can then find all words, in any order, without interruption.

In other words, given the string redgreenblue and the words ['red', 'green'] , you would return [0] , as you can find all of the words uninterrupted at that point. If instead the string was redgreengreenred , then you’d return [0, 8] as the combination of provided words can also be found at the end of the string.

Solution #1: Recursion

The basic premise for this solution is that we loop through the original string, and for each iteration, check if all of the target words can be found from this point on in the string. To achieve the more complicated latter half of this, we will use recursion.

The recursive function doesStringContainAllWords, takes a string and array of words, and checks if any of those words are found at the front of the string. If they are, we call the function again, providing the same string but moved on by the length of the word we found, and the same array of words, minus the found one. Once all words have been found, we confirm that the original string did contain all target words.

To speed things up with this overall approach, we also initially calculate the total length of all words being looked for. This allows us to exit early when we traverse far enough into the string to know that an answer can no longer be found.