Word Break II

The problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct sentences where each word is a valid dictionary word.

Function: def wordBreak(s,wordDict):

Example input (a JSON list of arguments): ["catsanddog", ["cat", "cats", "and", "sand", "dog"]]
Expected output: ["cat sand dog", "cats and dog"]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Memoize the valid sentence suffixes beginning at each string position.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def wordBreak(s,wordDict):
    from functools import lru_cache
    words=set(wordDict)-{''}
    @lru_cache(None)
    def visit(i):
        if i==len(s):return ['']
        return [s[i:j]+(' '+tail if tail else '') for j in range(i+1,len(s)+1) if s[i:j] in words for tail in visit(j)]
    return visit(0)

Why it works

Memoize the valid sentence suffixes beginning at each string position. Test dictionary prefixes and combine each with completed suffixes; empty dictionary words are excluded to prevent non-progressing recursion.

Complexity: Output-sensitive exponential time / memo and output space.

Time: Output-sensitive exponential time · Space: memo and output space