NOTE: I had the problem flipped. This solution below assumes I need to complete all the dictionary words with the string. I actually need to complete the string using any or all of the words in the dictionary. My solution works to solve the problem I had in mind, but it doesn't work to solve the actual problem. I am keeping this for posterity, but will restart this problem in a new post.
With this problem, I have a string and an array of words. I need to determine if the words in the array exist somewhere in the string. The words can overlap.
I'm thinking the plan is to iterate through the string once, and for each char, check to see if it belongs to an unfound word in the dict - be it the first letter or a subsequent letter in the existing word. If I'm not mistaken, the complexity here would be O(N*W) where n represents the number of letters and W represents the number of words in the dictionary array.
Thinking this out - we start at the beginning of the array. We compare the first letter against every word in the dictionary's first letter to see if there are any matches. If there are, I'll need to store the in progress letter with every word that begins with said letter. The next letter, I'll check to see if it either starts any word or is the next letter for an in-progress word. If the word is Aarvark, for example, the first a found would start the word. The second a found would continue the word, but also start the word, as this A may turn into the start of the word. We'll have to keep this state.
Keeping with Aardvark, if the first letter is a, we store the a with the word. If the next letter is anything but a, then we must remove the progress made toward Aardvark.
As we walk through the string, we'll need a way to check if a full word is found. Once a word is found, it should be removed from the list outstanding candidates and added to a found list, both so we can stop trying to find already found words, but also so we can early-out if we have already found all the words we need to find.
I think I've got enough of a grasp to start coding.
I'll iterate through the string with a while loop, so while i is less than the length of the string minus one OR foundStrings is equal to the goal strings passed into the function. The easiest way to do it would be to confirm the lengths of the arrays are the same, which would require me to ensure I'm never adding duplicate found words to the found array.
So for each index i, get the letter from the string index. Compare this letter against -
The first letter of all unfound words
the next letter of any in-progress string
Add the matching letters to either start or continue the in progress strings. On letter addition, evaluate the word for whether or not it's been completely found. If it has, move it to the found array and remove it from the candidates array.
On second thought - I don't even need the found array. I can simply remove the word from the candidates array.