题目

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

说明：

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

示例 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"]
输出:
[]

分析

先使用139题的方法判断是否可达，可达就用DFS进行搜索。

代码

class Solution {
public:
    vector<vector<int>> dp;
    vector<string> res;

    vector<string> wordBreak(string s, vector<string>& words) {        

        if (wordBreak_help(s, words)){
            dfs(s, "", -1);
        }
        return res;
    }

    void dfs(string s, string str, int start){

        if (start == s.size() - 1){
            res.push_back(str);
            return;
        }

        for (int i = start + 1; i < dp[start + 1].size(); i++){
            if (start + 1 < s.size() && dp[start + 1][i] == 1){
                string next_str;
                if (start + 1 == 0){
                    next_str = str + s.substr(start + 1, i - start);
                }else{
                    next_str = str + " " + s.substr(start + 1, i - start);
                }
                dfs(s, next_str, i);
            }
        }

        return;
    }

    bool wordBreak_help(string s, vector<string>& words) {

        set<string> st;
        for (auto w : words){
            st.insert(w);
        }

        int len = s.size();

        dp = vector<vector<int>>(len, vector<int>(len, 0));
        vector<int> this_dp(len, 0);

        for (int i = 0; i < len; i++){
            for (int l = 1; i + l - 1 < len; l++){

                int j = i + l - 1;

                string str = s.substr(i, l);

                if (st.count(str) != 0){
                    dp[i][j] = 1;           
                    if (i == 0 || i - 1 >= 0 && this_dp[i - 1] == 1){
                        this_dp[j] = 1;
                    }
                }
            }
        }

        return this_dp[len - 1] == 1 ? true : false;
    }
};