• 139.单词拆分
  • 题目
  • 题解

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];
    }
}