LC 139单词拆分Word Break　中等

判断字符串 s 能否由词典中的单词拼接而成，单词可重复使用。

思路 dp[i] 表示前 i 个字符可拆分，枚举最后一个单词起点 j：dp[j] 且 s[j:i] 在词典中则 dp[i] 为真。时间 O(n²)。

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