leetcode 139. 单词拆分

2023.8.18

        本题可以看作完全背包问题，字符串s为背包，字符串列表worddict中的字符串为物品。由于本题的物品集合是排列问题(即物品的排列顺序对结果有影响)，所以遍历顺序为：先遍历背包再遍历物品。

        接下来看代码：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size(),false);dp[0] = true;unordered_set<string> set(wordDict.begin(), wordDict.end());for(int j=1; j<=s.size(); j++){for(int i=0; i<=j; i++){string word = s.substr(i , j-i); //第二个参数代表长度if(dp[i] && set.find(word) != set.end()){dp[j] = true;}}}return dp[s.size()];}
};