问题是这样的:
Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string.
问题可以用递归/动态规划来解决,但是在分析时间复杂度的时候,一头雾水:
想象字典包含所有可能的字符排列(每个字符序列都是一个有效的单词),然后给定字符串,对于 2 个字符之间的每个位置,您可以选择是否插入空格,有n-1个这样的位置,所以有2^(n-1)种可能的结果。生成这些结果的任何算法的复杂度必须至少为 O(2^n)。
我可以使用动态规划算法来做到这一点。假设result[i]是子串i..N的可能拆分,计算result[j]:
k 在 j+1 到 N 范围内: 如果 s[j:k] 是一个有效的词: 合并结果中的单词[k]
由于我们是将result[N]计算回result[0],而这些计算每一次都需要O(N)(因为我们依赖的子问题已经计算完毕),所以时间复杂度应该是O(N^2) .
为什么我从2种推理中得出不同的结论,哪种是正确的?
最佳答案
除了输入字符串 n
的大小,您还应该引入一个额外的参数 r
来表示结果的大小,并在您的分析中使用它。在这种情况下,“结果的大小”类似于每个有效组合中单词数的总和。
在您对算法的描述中,您掩盖了如何将中间结果合并到循环体中。您隐含地假设这可以在恒定时间内完成。然而,正如您所指出的,这会导致矛盾的结果。
如果将算法分为两个阶段,分析会更简单:
在第一阶段,您将构建一个数据结构,指示可以在字符串中嵌入单词的位置。这可以在
Θ(n^2)
时间内完成,假设您可以检查每个子字符串是否是分摊常数时间内的单词。在第二阶段,您遍历此数据结构以输出单词组合列表。这可以在输出大小的线性时间内完成,
Θ(r)
。
所以总的来说,这个算法的时间复杂度为 Θ(n^2 + r)
。
注意:为了形式上正确,您还应该考虑阅读英语单词列表所需的时间。如果您想考虑这一点,您可以引入一个额外的变量 d
并在时间复杂度中添加一个 + d
项。
此外:可以通过使用 Aho-Corasick algorithm 改进此绑定(bind)的 n^2
部分查找所有匹配的子字符串,而不是在哈希表中查找每个子字符串。
关于algorithm - 将字符串分解为有效单词的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36882117/