题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
思路
这道题和 2369. 检查数组是否存在有效划分类似，都是划分型 DP 的题目，它的做法也很简单，用 dp[i+1] 表示从 s[0] 到 s[i] 的字符是否能被划分，dp[0] 代表空串，默认为 True。
与 2369 划分数字不同的是，这道题要求我们划分单词，在划分的时候可能会有很多种状态，因此我们可以在划分 s[0:i] 的时候用一个指针 j 去划分，判断 s[0:j] 和 s[j:i] 能否被划分，能的话就给相应的值赋值为 True。那么这样的动态规划方程为：
dp[i]=dp[j] && s[j:i] in wordDict
PS：此时 s[j:i] 只取到 s[:-1]，因此是 dp[i]。
最终代码：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
st = set(wordDict)
n = len(s)
dp = [True] + [False]*n
for i in range(n+1):
for j in range(i):
if dp[j] and s[j:i] in st:
dp[i] = True
break
return dp[n]