LeetCode 139 单词拆分

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串互不相同

动态规划

将问题转化为完全背包问题：此处的背包问题并不是求解最优化，而是判断能否将背包装满。但是此处的背包不同于之前的背包，背包中装入的必须是特定的元素。

此处需要判断的是能否恰好装满，若是先遍历物品，再遍历背包，那么实际上限制了物品元素的使用。（本质上是一个排列问题，元素在背包中有序）

考虑这样一种情况： s="applepenapple" wordDict=["apple","pen"] 那么先遍历物品，再遍历背包，初始时只能使用 apple 那么只能将第一个 apple 恰好装满，在第二次迭代中，是只考虑增加 pen 的情形，但实际上还需要使用 apple 对尾部进行装填，也就是每次向背包中装入时，需要使用到全部的物品，所以应该先遍历背包再遍历物品。

动态规划数组的定义：定义数组 dp[s.size()+1] 表示长度为 s.size() 的字符串能否恰好装满
动态规划数组的推导：在第 j 次迭代中，判断字符从 0-j-1 位置的字符串 s 能否恰好装满，对于每一个物品 wordDict[i] 都需要尝试从 j-1 处向前装入试试，所以有：其中 match 是字符串匹配操作。

1
2
3

if(j>=wordDict[i].size()){
    dp[j]=dp[j]||(dp[j-wordDict[i].size()]&&match(s,j-1,wordDict[i]));
}

动态规划数组的初始化：对于dp[0] 一定是能够恰好装满的，所以 dp[0]=true 其他全部初始化为 false
动态规划数组的遍历顺序：此处采取先遍历背包，再遍历物品的方式，物品和背包都采取从前向后遍历的方式
举例验证：对于 s="applepenapple" wordDict=["apple","pen"] 动态规划数组的推导过程为：验证成立

1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,0,
1,0,0,0,0,1,0,0,1,0,0,0,0,1,

代码实现：

class Solution {
public:
    bool match(string& s,int j,string& word){
        for(int i=0;i<word.size();i++){
            if(word[i]!=s[j-word.size()+1+i])
                return false;
        }
        return true;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int j=1;j<=s.size();j++){
            for(int i=0;i<wordDict.size();i++){
                if(j>=wordDict[i].size()){
                    dp[j]=dp[j]||(dp[j-wordDict[i].size()]&&match(s,j-1,wordDict[i]));
                }
            }
        }
        return dp[s.size()];
    }
};

Mark's blogs

LeetCode-139-单词拆分

LeetCode 139 单词拆分

动态规划