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

Question

问题陈述：给定一个非空字符串s和一个包含非空单词列表的字典字词，在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的长度。谁能帮我证明时间和空间的复杂性？

我还有以下几个问题：

• 如果我不在GetAllSences函数中使用memo，那么在本例中时间复杂度是多少？
• 还有比这更好的解决方案吗？

Answer 1

让我们试着一步一步地通过算法，但为了简化具体的单词来简化事情。因此，让wordDict是从a到z的所有字符，wordDict=[“a”,...,“z”]在本例中，如果（words.count（curWord））在i=0时每次都为true，否则为false。另外，让我们跳过使用备忘录缓存（我们稍后将添加它）。

在上面的例子中，我们只是递归地通过string s直到我们到达最后，除了结果向量之外，没有任何额外的内存，结果向量给出如下：时间复杂度为O（N！）空间复杂度为O(1)-当s的n列时，只存在1个解

现在让我们研究一下在我们的案例中使用备忘录缓存是如何改变情况的。Cache将包含n个项--字符串的大小是s，这将空间复杂度改为O(n)。我们的时间是一样的，因为每一个将没有点击使用备忘录缓存。

这是我们继续前进的基础。

现在，让我们试着找出如果wordDict包含所有字母对（s的长度是2*，所以我们可以到达结尾），事情是如何改变的。因此，wordDict=['aa','ab',...,'zz']在本例中，我们向前移动2个字母，而不是1，其他一切都是相同的，这给了我们使用备注缓存的oug以下复杂性：时间复杂性是O((n/2)！）空间复杂度为O(1)-只存在1个解

备忘录缓存将包含(n/2)项，给出一个O(n)的复杂度，这也将空间复杂度改变为O(n)，但那里的所有检查都有不同的长度。

现在让我们假设wordDict包含前面提到的两个词典('a'...'z'、'a'...'zz')。

在这种情况下，我们有以下复杂度，不使用备忘录缓存时间复杂度是O(n)！）因为我们需要检查i=0和i=1，这使得我们每一步需要做的检查数量增加了一倍，但在另一个大小上，它减少了我们以后必须做的检查数量，因为我们向前移动了2个字母，而不是一个字母（这是我最棘手的部分）。空间复杂度为~O(2^n)，因为每增加一个字符，结果数就增加一倍。现在让我们想想我们拥有的备忘录缓存。对于每3个字母都是有用的，因为例如“...ab c...”给出了与“...a bc...”相同的结果，因此它在每一步中减少了2个计算量，因此我们的复杂度将是以下时间复杂度大致为O((n/2)！）我们需要O(2*n)=O(n)内存来html" target="_blank">存储备忘录。我们还要记住，在n/2中，表达式2反映了缓存的有效性。空间复杂度是O(2^n)-2这里是我们构造的单词的一个特征

这是3个案例，我们可以了解复杂度是如何随着凝固剂的变化而变化的。现在让我们试着把它推广到一般情况下：

时间复杂度为O((N/(L*E))！）其中l=wordDict中单词的最小长度，e-cache有效性（在一般情况下我假设它为1，但在bt情况下，它可能不同，正如我们在上面的情况中看到的那样

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

这就是我如何看待你的方法和它的复杂性。

至于改进解决方案本身，我看不到任何简单的改进方法。也许有一种替代方法可以将字符串分成3个部分，然后分别处理每个部分，但如果我们可以摆脱搜索结果，只计算结果的数量而不显示它们，那么它肯定会奏效。

希望能有所帮助。