题目描述
给你一个字符串 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]
。
最终代码: