以下解决方案的时间和空间复杂度是多少？

Question

问题陈述：给定一个非空字符串s和一个包含非空词列表的字典wordDict，在s中添加空格，构建一个句子，其中每个词都是有效的字典。给定一个非空字符串s和一个包含非空词列表的字典wordDict，在s中添加空格来构造一个句子，其中每个词都是一个有效的字典词。返回所有这种可能的句子。

注释。

词典中的同一个词在分割过程中可能会重复使用多次.你可以假设词典中不包含重复的词.

测试案例示例。

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
 "cats and dog",
 "cat sand dog"
]

我的解决方案：

class Solution {
    unordered_set<string> words;
    unordered_map<string, vector<string> > memo;
public:

    vector<string> getAllSentences(string s) {
        if(s.size()==0){
            return {""};
        }
        if(memo.count(s)) {
            return memo[s];
        }
        string curWord = ""; vector<string> result;
        for(int i = 0; i < s.size(); i++ ) {
            curWord+=s[i];
            if(words.count(curWord)) {
                auto sentences = getAllSentences(s.substr(i+1));

                for(string s : sentences) {
                    string sentence = curWord + ((int)s.size()>0? ((" ") + s) : "");
                    result.push_back(sentence);
                }
            }
        }

        return memo[s] = result;
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for(auto word : wordDict) {
            words.insert(word);
        }

        return getAllSentences(s);
    }
};

我不确定时间和空间的复杂度. 我认为它应该是2^n，其中n是给定字符串s的长度，有人能帮我证明时间和空间的复杂性吗？

我还有以下几个问题。

• 如果我在getAllSentences函数中不使用memo，在这种情况下时间复杂度会是多少？
• 有没有比这更好的解决方案？

Answer 1

让我们试着一步步地完成这个算法，但是为了简化事情，让wordDict是从a到z的所有字符，wordDict = ["a",..., "z"]在这种情况下，if(words.count(curWord))将在每次i = 0时为true，否则为false.另外，让我们跳过使用备忘录缓存(我们将在后面添加)。

在上面的例子中，我们只是递归地得到了字符串s，直到我们到达终点，除了结果向量之外，没有任何额外的内存，这给出了以下结果：时间复杂度是O(n!)空间复杂度是O(1)--只有1个解存在其中n--s的长度。

现在让我们来看看在我们的情况下，使用备忘录缓存是如何改变情况的。缓存将包含n个项目--我们的字符串s的大小，这改变了空间复杂度为O(n)。我们的时间是一样的，因为使用memo cache不会有任何点击。

这是我们前进的基础。

现在让我们试着找出如果wordDict包含了所有的字母对（s的长度是2*something，所以我们可以到达终点），那么wordDict = ['aa','ab',...,'zz']在这种情况下，我们用2个字母而不是1个字母前进，其他的一切都一样，这给了我们以下的复杂度与使用备忘录缓存：时间复杂度是O((n2)!)空间复杂度是O(1)-只有1个解决方案存在

Memo cache将包含(n2)项，给出的复杂度为O(n)，这也将空间复杂度改为O(n)，但那里的所有检查都是不同长度的。

现在让我们想象一下，wordDict包含了我们之前提到的两个字典（'a'...'z'，'aa'...'zz'）。

在这种情况下，如果不使用memo cache，我们有以下复杂度：时间复杂度是O((n)!)，因为我们需要检查i=0和i=1的情况，这大约是我们每一步需要做的检查数量的两倍，但在另一个尺寸上，它减少了我们以后必须做的检查数量，因为我们向前移动了2个字母而不是1个(这是对我来说最棘手的部分)。它对于每3个字母都是有用的，因为例如'...ab c...'的结果和'...a bc...'的结果是一样的，所以它在每一步都减少了2个计算结果，所以我们的复杂度如下时间复杂度大约是O((n2)!)我们需要O(2*n)=O(n)内存来存储备忘录。我们还要记住，在n2表达式中，2反映了缓存的有效性.空间复杂度是O(2^n)-2这里是我们构建的wordDict的一个图示

这3个案例让我们了解了复杂度是如何根据情况变化的。现在让我们试着把它归纳为一般情况。

时间复杂度是 O((n(l*e))! 其中l = wordDict中单词的最小长度，e - 缓存效率(一般情况下我假设它是1，但也有可能出现不同的情况，就像我们在上面的案例中看到的那样)

空间复杂度是 O(a^n) 其中a是我们wordDict中单词的相似度，可以非常非常粗略地估计为P(hl)=(hl)！其中h是字典中最大的单词长度，l是最小的单词长度，为（例如，如果wordDict中包含了所有最多3个字母的组合，这就给我们提供了3个！每6个字母的组合）。

这是我对你的方法和它的复杂性的看法。

至于改进解决方案本身，我看不出有什么简单的方法可以改进它。可能有一个替代的方法，就是把字符串分成3部分，然后分别处理每一部分，但如果我们能摆脱搜索结果，只计算结果数量而不显示结果，那肯定能行。

希望对大家有所帮助。