题目内容

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

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

示例

示例 1：

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

示例 2：

输入:
s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
输出:
[
“pine apple pen apple”,
“pineapple pen apple”,
“pine applepen apple”
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

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

题解

本题使用动态规划和深度优先搜索算法求解。

首先，我们使用上一题的动态规划思想预处理F[i]，用于表示F[i,n]是否可以被完整分割。

然后，使用dfs进行搜索可能的分割方案。u代表搜索到s串的第几个字符，path代表分割的方案。

具体，请看代码。

代码

class Solution {
public:
    vector<bool> f;
    vector<string> ans;
    unordered_set<string> hash;
    int n = 0;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        f.resize(n + 1);
        for(auto word:wordDict) hash.insert(word);//初始化哈希表
        f[n] = true;
        for(int i = n - 1; ~i;i--){
            for(int j = i; j < n;j++)
                if(hash.count(s.substr(i,j - i + 1)) && f[j+1])
                    f[i] = true;
        }
        dfs(s,0,"");
        return ans;
    }

    void dfs(string& s,int u, string path){
        if(u == n){
            path.pop_back();//去掉最后一个空格
            ans.push_back(path);
        }else{
            for(int i = u; i < n;i++){
                if(hash.count(s.substr(u,i - u + 1)) && f[i + 1])
                    dfs(s,i+1,path+s.substr(u,i-u+1)+' ');
            }
        }
    }
};