个人网站教程,南昌企业网站设计公司,html5响应式企业网站,做网站编程在本题中#xff0c;我们是要把一个字符串#xff0c;判断是否能用给的字符串数组中的单词进行拆分#xff0c;如果可以则返回true#xff0c;不能的话则返回false。这个题一开始看无法与背包问题联系在一起。但仔细考虑#xff0c;就是用物品#xff08;给的字符串数组中… 在本题中我们是要把一个字符串判断是否能用给的字符串数组中的单词进行拆分如果可以则返回true不能的话则返回false。这个题一开始看无法与背包问题联系在一起。但仔细考虑就是用物品给的字符串数组中的单词去装背包给定的字符串。如果可以凑成那么就返回true。
并且题目中所说的单词可以重复使用也就是完全背包问题。并且我们要考虑这个题是否需要考虑遍历顺序拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。
“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。
“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。 所以我们要先遍历背包再遍历物品。并且可以重复使用
dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词
如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
那么dp[0]有没有意义呢
dp[0]表示如果字符串为空的话说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString 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; j) {if (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}
}注意本题中创建了一个新的 HashSet 实例并使用 wordDict 集合的元素进行初始化。这意味着 set 中的所有元素都将是 wordDict 中的元素但不包含任何重复项因为 HashSet 是一个不允许重复元素的集合。 s.substring(j,i)表示截取字符串s下标从j到i的字串这里是左闭右开的区间。所以j只能小于i如果等于i的话下面截取的时候就会出错。
