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

说明：

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

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

我的代码 12ms

static int x=[](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
class Solution {
public:
    void dfs(string s,string temp,vector<string> &solution,unordered_set<string> &u_s)
    {
        if(s=="")
            solution.push_back(temp);
        for(int i=1;i<=s.size();i++)
        {
            
            string s1=s.substr(0,i);
            if(u_s.count(s1)==1)
            {
                string s_t=temp;
                if(temp.size()!=0)
                    s_t+=" ";
                s_t+=s1;
                string s2=s;
                s2.erase(0,i);
                dfs(s2,s_t,solution,u_s);
            
            }
        }

        
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> solution;
        unordered_set<string> u_s;
        unordered_set<char> alphabet;
        vector<int>f(s.size(),0);
        string temp;
        int minl=1e9;
        int maxl=0;
        int max_ok=0;
        for(int i=0;i<wordDict.size();i++)
        {
            u_s.insert(wordDict[i]);
            for(int j=0;j<wordDict[i].size();j++)
                alphabet.insert(wordDict[i][j]);
            if(wordDict[i].size()<minl) minl=wordDict[i].size();
            if(wordDict[i].size()>maxl) maxl=wordDict[i].size();
        }
        for(int i=0;i<s.size();i++)
            if(alphabet.count(s[i])==0) return solution;
        for(int i=minl-1;i<s.size();i++)
        {
            for(int j=minl;j<=maxl&&(i-j+1)>=0;j++)
            {
                int p=i-j+1;
                string s1=s.substr(p,j);
                if(u_s.count(s1)==1)
                {
                    if(p==0) 
                    {
                        f[i]=1;
                        break;
                    }
                    else if(f[p-1]==1)
                    {
                        f[i]=1;
                        break;
                    }
                }
            }
        }
        if(f[s.size()-1]==0) return solution;
        dfs(s,temp,solution,u_s);
        return solution;
        
    }
};

最优代码 4ms

class Solution {
public:
	vector<string> wordBreak(string s, vector<string>& wordDict) {
		int n = s.length();
		unordered_set<string> st;

		// dp[j], 记录长度为 j 的串，以 j 为结尾的哪些后缀在字典中。
		vector<vector<int>> dp(n + 1);

		dp[0] = { 0 };

		int minLength = INT_MAX;
		int maxLength = 0;

		// Step 1. 追踪字典中最短的单词和最长的单词，并插入 set
		for (auto& word : wordDict) {
			if (word.length() < minLength) minLength = word.length();
			if (word.length() > maxLength) maxLength = word.length();
			st.insert(word);
		}

		// m[i] 表示长度为 i 的串构造的句子
		vector<vector<string>> m(n + 1);

		// Step 2.计算长度为 i 的串是否能被拆分
		for (int j = 1; j <= n; ++j) {
			for (int i = max(0, j - maxLength); i <= j - minLength; ++i) {
				if (!dp[i].empty() && st.count(s.substr(i, j - i))) {
					dp[j].push_back(i);
				}
			}
		}

		// 提前剪枝
		if (dp[n].empty()) return vector<string>();

		// Step 3. 下面这段不能合并到 Step 2 中，否则会超时。这里正好可以用到 Step 2 结果。当然你也可以使用 dfs，那就得再遍历一遍串，并且查找 dict，费事。
		for (int j = 1; j <= n; ++j) {
			if (dp[j].empty()) continue;
			for (auto i : dp[j]) {
				if (m[i].empty()) {
					m[j].push_back(s.substr(i, j - i));
				}
				else {
					for (auto& ss : m[i]) {
						m[j].push_back(ss + ' ' + s.substr(i, j - i));
					}
				}
			}
		}

		return m[n];
	}
};