一句话总结:完全背包!
原题链接:139 单词拆分
动态规划之完全背包五部曲:
- 确定dp数组与下标含义:表示字符串长度为i时,dp[i] == true 的话,可以拆分为一个或多个在字典中出现的单词。
- 确定递归公式。当且仅当同时满足dp[j] == true && set.contains(substr(j ,i)),dp[i] = true;
- 动规数组的初始化。从递推公式可以看出dp[0] 必须为true,否则后面所有的dp[i]都将为false。
- 递推的遍历顺序。因为字符串的字符存在顺序,因此求的是排列数,所以遍历顺序为:外层循环遍历背包容量,内层循环遍历物品。由此4步即可确定整体代码如下。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i && !dp[i]; j++) {
if (set.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
}