Split a Sentence into Words

Coupa Software may receive normalized text where a sentence contains only lowercase letters and no spaces or punctuation. Given the text and a dictionary of valid words, return any valid sequence of dictionary words that reconstructs the entire input. Return an empty list if no segmentation exists.

Use a combination of a trie and dynamic programming. The trie should make it efficient to discover dictionary words beginning at each reachable position, while dynamic programming should prevent repeated exploration of the same suffix.

Formal Specification

Implement split_sentence(s, word_dict).

• s is a lowercase string.
• word_dict is a list of unique lowercase strings.
• Return a list of strings whose concatenation equals s.
• Every returned string must occur in word_dict.
• If multiple segmentations exist, return any one. If none exists, return [].