139. 单词拆分

完全背包，某一特定的排列

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string>uset(wordDict.begin(), wordDict.end());
        vector<bool> dp(n + 1);
        dp[0] = true;
        // 要排列  先背包再物品
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 0; j < wordDict.size(); j ++)
            {
                int len = wordDict[j].size();
                if (i >= len)
                {
                    if (uset.count(s.substr(i-len, len)) && dp[i-len])
                        dp[i] = true;
                }
            }
        }
        return dp[n];
    }
};