Create valid sentences from the initial string and the word directory provided.
If the word is "catsdogsgoats" and the word dictionary is "cats", "cat", dogs" and "goats" Then we need to check for all words which are valid and maybe a starting word. For example the word "cat" is a starting word, same as "cats" So the word can be any word of the dictionary, we do not know.
I was thinking I will create a trie like data structure and then keep a map of stuff. Too complicated.
The solution is to observe recursion and manipulation, in step 2 I said "do the same thing for the rest of the string" that's sound like a recursion
So get a starting word and call the function f(remaining word) The return will be a list of valid sentences of remaining word
So the resultant will be word + each of the valid sentences of the remaining word
So loop through f(remaining words) and prepend the first word in each case
So we needed to construct sentence like word1word2word3 So he checked if word.isEmpty() ? "": " " + word
Good solution, but we can just do trim at the end, not a great use case but still good tool to have.