代码随想录day40：动态规划part8，背包问题完
文章目录
- day40：动态规划part8，背包问题完
- 139.单词拆分
day40：动态规划part8，背包问题完
139.单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// dp[i]：字符串长度为i时，dp[i] true/false 表示是否可以拆分
HashSet<String> set = new HashSet<>(wordDict);
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i && !valid[i]; j++)
if (set.contains(s.substring(j, i)) && valid[j])
valid[i] = true;
}
return valid[s.length()];
}
}
背包问题需要重新梳理总结！
待更新！！