# LC139. Word Break

Link to problem: https://leetcode.com/problems/k-closest-points-to-origin/

We solve this type of problems with dynamic programming. Let `dp[i]`

be the boolean whether `s[0..i-1]`

can be broken into valid words in `wordList`

, then we have `dp[i] = any(dp[j] and (s[j..i-1] in wordList)) for 0 <= j <= i`

, i.e. whether we can find some index `j`

that is less than or equal to `i`

such that `s[0..j-1]`

can be split into words and `s[j..i-1]`

is also a valid word. Specially, we assign `dp[0] = true`

, as we do not need to worry about an empty string not being in `wordList`

.

The 1D DP algorithm uses $\O(n)$ space. Since we need to traverse the previous part of the array for every index, the time complexity is $\O(n^2)$.

我们可以用动态规划来解决这一类问题。令 `dp[i]`

表示 `s[0..i-1]`

是否可以分割为 `wordList`

中的单词，那么有 `dp[i] = any(dp[j] and (s[j..i-1] in wordList)) for 0 <= j <= i`

，即是否能找到某个不超过 `i`

的下标 `j`

使得 `s[0..j-1]`

可以分割为单词且 `s[j..i-1]`

也是有效的单词。特别地，我们令 `dp[0] = true`

，因为我们不需要担心空的字符串不在 `wordList`

中。

使用一维 DP 的空间复杂度为 `len(dp)`

即 $\O(n)$，而时间复杂度由于对每个元素都需要遍历之前部分的数组，为 $\O(n^2)$。

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