题目内容

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

1、拆分时可以重复使用字典中的单词。
2、你可以假设字典中没有重复的单词。

示例

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

题解

本题采用动态规划求解。

首先，进行状态表示：

设F[i]表示在所有s串的1到i的所有合法的划分方案集合，F[i]的值代表集合是否非空。

然后，进行状态计算：

将集合按照最后一个单词的范围，划分为1到i，2到i，3到i，…，i到i。当然我们要清楚一点，就是最后一个划分的区域一定要在给定的字典中出现，因此我们在计算的时候，要每一次判断划分的区域是否在字典中出现。假设，划分到第k到i，在字典中出现过了，那么F[i] = F[k-1]||…。

我们只需要计算其中某一种划分情况存在就可以返回true。如果全部情况均不满足，我们就返回false。

另外，划分区间判断是否满足字典中的单词，我们采用字符串哈希的方式。字符串哈希的思想，见该处

具体，请看代码。

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;//定义一个无符号long long类型
        const int P = 131;//字符串hash的基础值
        unordered_set<ULL> hash;//存放hash值
      	//进行字符串hash
        for(auto& word:wordDict){
            ULL h = 0;
            for(auto c:word){
                h = h * P + c;
            }
            hash.insert(h);
        }
        int n = s.size();
        vector<bool> f(n+1);
        f[0] = true;
        s =' '+s;
      	//进行动态规划。这里的思想是已知1到i存在划分方案的情况下，去寻找后面i+1到s.size中可能存在的方案是否存在
        for(int i = 0;i < n;i++){
            if(f[i]){
                ULL h = 0; 
                for(int j = i + 1; j <= n; j++){
                    h = h * P + s[j];
                    if(hash.count(h)) f[j] = true;
                }
            }
        }
        return f[n];
    }
};