I considered splitting this into three separate posts but decided against it. Today's episode is going to through three iterations on the initial problem, each expanding on the last. So without further ado, here's the first problem...
“Build a function that, given a dictionary of words and a string without spaces, capitalization, or punctuation, returns whether the string is a complete sentence.”
So given the input: "thisisawesome" (which you can totally search for to find this question and solutions), and a dictionary of words that are contained within it, we'll want to iterate over the characters in the string until we find a word. At that point we'll have split our string into two parts: the left side with a known word, and the right that remains unknown.
If we use a recursive function to find the first complete word in a given string that returns "true" for a string length 0, we can use it to check the right side of each string split in the recursive stack until we either have nothing on the right, or some leftover characters that can't be parsed into words. When the latter happens we know we can't split the string into a complete sentence and should return false. Below is a solution.
And that's pretty simple, right? It's probably pretty obvious where our first expansion will be...
“Given the same string and dictionary, create a function that returns a possible sentence the string could be split into.”
Since we've already solved the first part, this next part isn't too difficult; we just need to keep track of the words on the left as we find them. Doing that with basically the same recursive strategy means we can add a result tracking parameter to the method signature and pass that plus the found word to each subsequent recursive call. The result when we unwind the stack will be a sentence split into the smallest possible words at every step. Check it out below.
The solution above is almost the same at the first iteration, just with added tracking. Instead of returning "true" though, we return our "result" tracking param. Since we still return false when we fail to split a string, this solution will either return a sentence, or "false".
Buuuuut "this is a we so me" isn't really the result we'd expect, is it? Time for one last expansion:
“Find a way to split the string into all possible complete sentences.”
This expansion isn't as bad as it sounds, and after going through the last two iterations it's pretty clear all we need to do is add an additional tracking param to the recursive function to keep an array of solutions from the result parameter.
The biggest difference is that we'll change up the break-out method for the recursion from a pre-check condition outside the loop, to a terminal check inside the loop. That's just saying that once we find the last word in the string we should push (unshift in the solution below) the sentence into the tracking array. Once we unwind the recursion, the tracking array will have all our possible sentences, and we can simply return it in all cases. Now since we're looking for all solutions, we can return an empty array when we don't find anything. Check it out below:
BAM. Kicked it up a notch. The reason I used "unshift" in the solution above is because the nature of our result tracker means we find the shortest words first, and therefor the sentences we find first have the most possible splits. Using "unshift" for the sentence tracker lets us return the strings with the least splits (and the most compound words) first, and makes it more likely the intended string is near the top of the result set.
But wait there's more! None of these can do much about a sentence that doesn't split properly besides fall out of the recursion. The last expansion is an exercise for the reader (mostly because I've run out of time). Good luck!
“Given that we now have a function that can find all possible complete sentences, modify it to return the “problem characters” for a string that does not split completely. These may appear in the middle of a string like, “thisisxawesome” or the middle of a word like, “thxisisawesome””