上海专业做网站公司,做网站前需要准备什么条件,单页网站技术,如何查看网站语言LeetCode 139. 单词拆分 题目链接#xff1a;139. 单词拆分 - 力扣#xff08;LeetCode#xff09;
这道题使用完全背包来实现#xff0c;我们首先考虑字符串是否可以由字符串列表组成#xff0c;因此dp数组大小为n 1 #xff0c;其意义是#xff0c;在n个位置时是否能…LeetCode 139. 单词拆分 题目链接139. 单词拆分 - 力扣LeetCode
这道题使用完全背包来实现我们首先考虑字符串是否可以由字符串列表组成因此dp数组大小为n 1 其意义是在n个位置时是否能拼接成功。因此当前n状态由前面状态所转移确定。
每道题都要考虑dp五步
1确定dp数组下标与值的关系处于n位时是否能拼接成功。
2确定递推公式我们把n个数的状态看作i之前j到i的字母是否能在字符串列表中存在
3确定初始值dp[0]为1,没得选
4确定遍历的数注意一下边界问题
5带入验证一下
代码
#python //一维DP
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:n len(s)dp [0 for _ in range(n 1)]dp[0] 1 //由空集可以组成for i in range(1, n 1):for j in range(i 1): //注意i与j的位置来确定在字符串中子串的边界从而来判断是否在列表中if dp[j] 1 and str(s[j : i]) in wordDict:dp[i] 1 //满足return bool(dp[n]) //返回布尔值
