题目

题目连接

给定一个字符串 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"]
输出:[]

解题

方法一：哈希集合+dfs

class Solution {
    
public:
    vector<string> res;
    unordered_set<string> set;
    void dfs(string& s,int startIndex,string&& path){
    
        if(startIndex==s.size()){
    
            res.push_back(path);
            return;
        }else if(startIndex!=0) path+=" ";//头部和尾部不用加空格

        for(int i=startIndex;i<s.size();i++){
    
            string tmp=s.substr(startIndex,i-startIndex+1);
            if(set.count(tmp)){
    
                dfs(s,i+1,path+tmp);//以形参方式带入，就不需要手动回溯了
            }
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
    
        set=unordered_set<string>(wordDict.begin(),wordDict.end());
        dfs(s,0,"");
        return res;
    }
};

方法二：字典树+dfs

class Trie{
    
public:
    bool isEnd=false;
    vector<Trie*> next=vector<Trie*>(26,nullptr);
};


class Solution {
    
public:
    Trie* trie=new Trie();
    vector<string> res;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
    
        for(string& word:wordDict){
    
            insert(word);
        }
        dfs(s,0,"");
        return res;
    }

    void dfs(string& word,int startIndex,string&& path){
    
        if(startIndex==word.size()){
    
            res.push_back(path);
            return;
        }else if(startIndex!=0) path+=" ";
        Trie* node=trie;
        string tmp="";
        for(int i=startIndex;i<word.size();i++){
    
            char c=word[i];
            tmp+=c;
            if(node->next[c-'a']) node=node->next[c-'a'];
            else return;
            if(node->isEnd){
    
                dfs(word,i+1,path+tmp);
            }
        }
    }

    void insert(string& word){
    
        Trie* node=trie;
        for(char c:word){
    
            if(node->next[c-'a']==nullptr){
    
                node->next[c-'a']=new Trie();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }
};