LeetCode 139: Word Break

Note, word = “” + word is a valid segmentation as long as word is in wordDict.

Dynamic programming

Subproblem

Let $W(i)$ denote if the prefix $s[1 \ldots i]$ can be broken into words. Then:

$W(i) = \begin{cases} \bigvee\left( \left\{ W(j) \wedge s[j+1\ldots i] \in \texttt{words} \ | \ 1 \le i \le n, j \le i \right\} \right), & \text{if } j > 0 \\ \texttt{true} & \text{otherwise} \end{cases}$

Note, we assume an empty string can be segmented.

Order

Edges go from smaller $i$ ‘s to a bigger $i$ . Processing in the order of increasing $i$ gives us a topological order.

There are $\mathcal{O}(n)$ subproblems. The $i$ -th subproblem depends on $i$ earlier subproblems each of which requires a str-slicing. So, total time: $\mathcal{O}(n^3)$ , space: $\mathcal{O}(n)$ .

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        word_set = set(wordDict)
        dp = [True] + [False]*n
        for i in range(1, n+1):
            for j in range(i, 0, -1):
                if dp[j-1] and s[j-1:i] in word_set:
                    dp[i] = True
                    break
        return dp[n]

Trie

If wordBreak() is called often with the same wordDict but for different s‘s, turning wordDict into a trie and reusing that trie might help.

unreasonably effective