139.单词拆分
题目
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapappleple" 可以被拆分成 " pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
从一个数组中按一定的选取方式得到目标，这道题看着像是满足的,那么尝试一下。
如果从背包问题的角度来看的话，背包应该是字符串s，物品是wordDict数组，数组中的元素按一定的排列方式填满背包。数组的里元素可以重复，是一个完全背包。
1.确定dp[i]及下标的含义
dp[i]=true 表示长度为i的字符串可以被空格拆分为一个或多个在字典中出现的单词。
2.确定递推表达式
dp[i]如何推导？
- 如果dp[j]=true,[j,i]这个区间的子串在wordDict数组中出现，则dp[i] = true
- 如果dp[j]=true,[j,i]这个区间的子串没有在wordDict数组中出现，则dp[i]=false
- 如果dp[j]=fasle,[j,i]这个区间的子串不管有没有在数组中出现，dp[i]=fasle
所以dp[i]为true只有一种情况，dp[j]=true,wordDict中contains的s.substring(j,i)子串。
3.dp数组初始化
dp[0]=true
如果dp[0]=false,那么不管[0,i]这个区间的子串是不是在数组中出现，dp[i]=false
4.确定遍历顺序
这道题无关与先遍历背包还是先遍历物品，把递推表达式翻译成代码就可以了。
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i]= true;
break;
}
代码
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean [] dp = new boolean[len+1];
dp[0] = true;
for(int i=1;i<=len;i++){
for(int j=0;j<i;j++){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i]= true;
break;
}
}
}
return dp[len];
}
}