140.单词拆分II

140. 单词拆分 II

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

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

提示：

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s 和 wordDict[i] 仅有小写英文字母组成
• wordDict 中所有字符串都 不同

C++

• 思路: DFS

class Solution {
public:
    vector<string> res;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        string path;
        dfs(s, wordDict, res, path);
        return res;
    }
    
    void dfs(string s, vector<string>& wordDict, vector<string>& res, string path){ 
        if(s.empty()){
            res.push_back(path);
            return;
        }
        set<string> st(wordDict.begin(), wordDict.end());
        int n = s.size();
        for(int L = 0; L < n + 1; L ++){
            if(st.find(s.substr(0, L)) != st.end()){
                string temp= s.substr(0, L);
                dfs(s.substr(L), wordDict, res, s.substr(L).empty() ? path + temp : path + temp + ' ');
            }
        }
    }
};

等价于

class Solution {
public:
    vector<string> res;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        string path;
        dfs(s, wordDict, path);
        return res;
    }
    
    void dfs(string s, vector<string>& wordDict, string path){
        if(s.empty()){
            res.push_back(path);
            return;
        }
        set<string> st(wordDict.begin(), wordDict.end());
        int n = s.size();
        for(int L = 0; L < n + 1; L ++){
            if(st.find(s.substr(0, L)) != st.end()){
                string temp= s.substr(0, L);
                dfs(s.substr(L), wordDict, s.substr(L).empty() ? path + temp : path + temp + ' ');
            }
        }
    }
};