Recursion
Imagine we have a set of words that constitute a vocabulary:
a
ate
dinner
for
ford
i
inner
night
noodles
oodles
ten
to
tonight
We can then make a phrase that uses these words but without any word breaks in it:
iatenoodlesfordinnertonight
That phrase can be successfully parsed into a number of phrases that use our vocabulary:
i a ten oodles for dinner to night
i a ten oodles for dinner tonight
i a ten oodles ford inner to night
i a ten oodles ford inner tonight
i ate noodles for dinner to night
i ate noodles for dinner tonight
i ate noodles ford inner to night
i ate noodles ford inner tonight
(While many of those aren’t logical English sentences, they all are made up of our words from our vocabulary).
In this challenge, you’ll build a function that is given a phrase and a vocab set. It should return a set of the possible legal phrases that can be made from that vocabulary.
For example:
>>> vocab = {'i', 'a', 'ten', 'oodles', 'ford', 'inner', 'to',
... 'night', 'ate', 'noodles', 'for', 'dinner', 'tonight'}
>>> sentences = parse('iatenoodlesfordinnertonight', vocab)
>>> for s in sorted(sentences):
... print s
i a ten oodles for dinner to night
i a ten oodles for dinner tonight
i a ten oodles ford inner to night
i a ten oodles ford inner tonight
i ate noodles for dinner to night
i ate noodles for dinner tonight
i ate noodles ford inner to night
i ate noodles ford inner tonight
We’ve given you a stub for this function:
def parse(phrase, vocab):
"""Break a string into words.
Input:
- string of words without space breaks
- vocabulary (set of allowed words)
Output:
set of all possible ways to break this down, given a vocab
"""
Complete it.