This function word_break(s, dictionary) receives a string s and a set of all valid words dictionary, and must return all possible ways the string s can be split into valid words, if any.

For example, a string catsanddog with dictionary {'cat', 'cats', 'sand', 'and', 'dog'} can be broken in two ways: cats and dog and cat sand dog.

My solution to this recursively breaks the input string at various index (offset), and uses memoization as I realized we may be breaking at the same offset multiple times.

Here is the full code along with a test case, in Python 2.x:

def memoize(fn):
    memo = {}
    def wrapped_fn(*args):
        if args not in memo:
            memo[args] = fn(*args)
        return memo[args]
    return wrapped_fn

def word_break(s, dictionary):    
    def _word_break(offset):
        if offset == len(s):
            return []

        breaks_from_offset = []
        if s[offset:] in dictionary:

        for i in range(offset+1, len(s)):
            if s[offset:i] in dictionary:
                for break_from_i in _word_break(i):
                    breaks_from_offset.append([s[offset:i]] + break_from_i)

        return breaks_from_offset

    return [' '.join(words) for words in _word_break(0)]

# print word_break('catsanddog', {'cat', 'cats', 'sand', 'and', 'dog'})
# -> [cat sand dog', 'cats and dog']

Based on LeetCode question Word Break II: https://leetcode.com/problems/word-break-ii/description/

As this is an "interview" algorithm question, I would love feedback that keeps that setting in mind. That said, I also appreciate any feedback to help me write more production-ready Python code :)


1 Answer 1


Honestly it looks like you're doing this wrong. Currently you're splitting the word into \$n^2\$ words and checking if they are in the dictionary. Rather than doing this you can traverse a Trie and loop through the input once. To do this you'd just need a 'partial words list' which is a set of Trie nodes. You then just need to make some lists for the output, and then return the one that you think is best. This can be a bit tricky to do, but the challenge is finding which output list(s) to append to, which you can do when adding new tries to the partial words list.

I'd implement this in the following way:

import collections.abc

class TrieNode(collections.abc.MutableMapping):
    def __init__(self, k):
        self._data = {}
        self._value = k
        self.end = False

    def build(iterable):
        root = TrieNode(None)
        for key in iterable:
            root[key] = True
        return root

    def value(self):
        return self._value

    def _keys(self, key):
        partial = ''
        for k in key:
            partial += k
            yield k, partial

    def _walk(self, data, key, *, build=False):
        if not key:
            raise ValueError()

        node = data
        if not build:
            for k in key[:-1]:
                node = node._data[k]
            for k, key_ in self._keys(key[:-1]):
                node = node._data.setdefault(k, TrieNode(key_))
        return key[-1], node

    def __getitem__(self, key):
        key, node = self._walk(self, key)
        return node._data[key]

    def __setitem__(self, key, value):
        k, node = self._walk(self, key, build=True)
        node = node._data.setdefault(k, TrieNode(key))
        node.end = value

    def __delitem__(self, key):
        key, node = self._walk(self, key)
        del node._data[key]

    def __iter__(self):
        return iter(self._data)

    def __len__(self):
        return len(self._data)

def word_break(word_string, words):
    words = TrieNode.build(words)
    output = {0: [[]]}
    partials = []
    for i, k in enumerate(word_string, 1):
        new_partials = []
        for partial in partials + [words]:
            partial = partial.get(k)
            if partial is None:

            if not partial.end:

            val = partial.value
            prevs = output.get(i - len(val))
            if prevs is not None:
                output.setdefault(i, []).extend([p + [val] for p in prevs])
        partials = new_partials
    return output[len(word_string)]

if __name__ == '__main__':
    words = word_break('catsanddog', {'cat', 'cats', 'sand', 'and', 'dog'})
  • \$\begingroup\$ Thanks for taking a look! I don't quite understand why Trie is better and how it fits in -- is it to save space? Can you explain what you had in mind, e.g. what is each Trie node? I'm already storing the "partial words list" for each offset, by memoizing. \$\endgroup\$
    – nycb
    Jun 30, 2018 at 23:31
  • \$\begingroup\$ @bcyn Each time you run the function you add more to memory, using a trie wouldn't do that. It also runs in \$O(n)\$ time, rather than \$O(n^2)\$, the only problem is it may be more confusing. But I'd find recursion more confusing any day. \$\endgroup\$
    – Peilonrayz
    Jul 1, 2018 at 0:24
  • \$\begingroup\$ I'll have a little more time to expand on this tomorrow \$\endgroup\$
    – Peilonrayz
    Jul 1, 2018 at 0:31
  • \$\begingroup\$ Got it, so something like storing pointers of the partial lists instead of the actual lists (what I’m doing)? \$\endgroup\$
    – nycb
    Jul 1, 2018 at 7:03
  • \$\begingroup\$ @bcyn I've added the code to show how I'd do it. \$\endgroup\$
    – Peilonrayz
    Jul 1, 2018 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.