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

class Solution:    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        ans = []        n = len(s)        def backtrack(temp, start):            if start == n: ans.append(temp[1:])            for i in range(start, n):                if s[start:i + 1] in wordDict:                    backtrack(temp + " " + s[start:i + 1], i + 1)        backtrack('', 0)        return ans

class Solution {    int maxLen = 0;    unordered_set<string> ws;    vector<int> m;    vector<string> ans;    bool dfs(string &s, int i, string tmp) {        if (i == s.size()) {            ans.push_back(tmp);            return true;        }        if (m[i] == 0) return m[i];        m[i] = 0;        for (int j = min((int)s.size(), i + maxLen); j > i; --j) {            auto sub = s.substr(i, j - i);            if (ws.count(sub) && dfs(s, j, tmp.size() ? tmp + " " + sub : sub)) m[i] = 1;        }        return m[i];    }public:    vector<string> wordBreak(string s, vector<string>& dict) {        ws = { dict.begin(), dict.end() };        for (auto &w : dict) maxLen = max(maxLen, (int)w.size());        m.assign(s.size(), -1); // -1 = unvisited, 0 = can not reach end, 1 = can reach end.        dfs(s, 0, "");        return ans;    }};

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"[  ("a",  "aa",  "aaa",  "aaaa",  "aaaaa",  "aaaaaa",  "aaaaaaa",  "aaaaaaaa",  "aaaaaaaaa",  "aaaaaaaaaa")];

{  hi: true,  h: true,  i: true,  world: true,  hello: true,}

class Solution:    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        n = len(s)        @lru_cache(None)        def backtrack(start):            ans = []            if start == n:                ans.append('')            for i in range(start, n):                if s[start:i + 1] in wordDict:                    if start == 0: temp = s[start:i + 1]                    else: temp = " " + s[start:i + 1]                    ps = backtrack(i + 1)                    for p in ps:                        ans.append(temp + p)            return ans        return backtrack(0)