139-单词拆分

LeetCode 139. Word Break

LeetCode-139

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

method: 完全背包

把字典里的字符串放进集合里，当成物品，可以无限使用，所以是完全背包

dp[i]：表示从0到i-1的子串能不能被组合，dp[i]为true，表示s[0:i-1]可以拆分为一个或多个在字典中出现的单词。

如果区间[j,i)的子串在集合中，并且dp[j]为true，那dp[i]也可以是true

因为是求背包能否装满，不是排列组合问题，所以先遍历背包还是先遍历物品都行，为了方便求子串，就先遍历背包

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> hash(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {   // 枚举字符串长度
        for (int j = 0; j < i; j++) {   // 枚举以s[i-1]结尾的所有子串
            string word = s.substr(j, i - j);   // [j,i)的子串
            if (hash.count(word) && dp[j])
                dp[i] = true;
        }
    }
    return dp[n];
}

结果

idx: 0 1 2 3 4 5 6 7 8
str: l e e t c o d e
dp : 1 0 0 0 1 0 0 0 1

dp[j]表示子串[0, j-1]能否被组成，而我们要算的是子串[j, i-1]在不在字典中，如果在字典中，并且前面的子串[0, j-1]也在字典中，也就是dp[j]=true，那合起来[0, i-1]这个长度为i的子串就也可以被组成，所以dp[i]=true