When expressing complexities, |s| is the length of `s`

, |d| is the length of `wordDict`

and m is the maximum length of the words in `wordDict`

.

**Prefix tree** - O(|d| m) setup + O(|s| |d|) runtime and O(|d| m) space.

```
class Solution(object):
def wordBreak(self, s, wordDict):
tree = {}
for word in wordDict:
branch = tree
for c in word:
branch = branch.setdefault(c, {})
branch[None] = None
possibilities = {id(tree): tree}
for c in s:
newpossibilities = {}
for p in possibilities.itervalues():
try:
branch = p[c]
except KeyError:
continue
if None in branch:
newpossibilities[id(tree)] = tree
if len(branch) == 1:
continue
newpossibilities[id(branch)] = branch
possibilities = newpossibilities
return id(tree) in possibilities
```

**Dynamic programming** - O(|s| m) time and O(1) time.

```
class Solution(object):
def wordBreak(self, s, wordDict):
wordDict = set(wordDict)
valid = [False] * (len(s) + 1)
valid[0] = True
for i in xrange(1, len(s) + 1):
for j in xrange(i - 1, -1, -1):
if valid[j] and s[j:i] in wordDict:
valid[i] = True
break
return valid[-1]
```