Hackbright Code Challenges

Word Break

Word Break

Whiteboard

Harder

Challenge

Medium

Concepts

Recursion

Download

word-break.zip

Solution

Word Break: Solution


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:

word_break.py
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.