代码随想录day46

139.单词拆分

单词就是物品，字符串就是背包，就是问能不能把背包填满，又因为可以重复使用，所以是完全背包。同时本题求的是排列，所以先遍历背包，再遍历物品（物品就是用substr截取出的字符串）。

因为要进行查找操作，所以先把字符串数组转换成set。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n=s.size();
        unordered_set<string> wordset(wordDict.begin(),wordDict.end());
        vector<bool> dp(n,false);
        dp[0]=true;
        //求排列，先遍历背包再遍历物品
        for(int i=1;i<=n;i++){//完全背包，正序遍历
            for(int j=0;j<i;j++){
                string word=s.substr(j,i-j);
                if(wordset.find(word)!=wordset.end()&&dp[j]){
                    dp[i]=true;
                }
            }
        } 
        return dp[n];
    }
};