algorithm - 将字符串分解为有效单词的时间复杂度是多少？

Question

问题是这样的:

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.

问题可以用递归/动态规划来解决，但是在分析时间复杂度的时候，一头雾水:

1. 想象字典包含所有可能的字符排列(每个字符序列都是一个有效的单词)，然后给定字符串，对于 2 个字符之间的每个位置，您可以选择是否插入空格，有n-1个这样的位置，所以有2^(n-1)种可能的结果。生成这些结果的任何算法的复杂度必须至少为 O(2^n)。

2. 我可以使用动态规划算法来做到这一点。假设result[i]是子串i..N的可能拆分，计算result[j]:

   k 在 j+1 到 N 范围内:
如果 s[j:k] 是一个有效的词:
合并结果中的单词[k]

   由于我们是将result[N]计算回result[0]，而这些计算每一次都需要O(N)(因为我们依赖的子问题已经计算完毕)，所以时间复杂度应该是O(N^2) .

为什么我从2种推理中得出不同的结论，哪种是正确的？

Answer 1

除了输入字符串 n 的大小，您还应该引入一个额外的参数 r 来表示结果的大小，并在您的分析中使用它。在这种情况下，“结果的大小”类似于每个有效组合中单词数的总和。

在您对算法的描述中，您掩盖了如何将中间结果合并到循环体中。您隐含地假设这可以在恒定时间内完成。然而，正如您所指出的，这会导致矛盾的结果。

如果将算法分为两个阶段，分析会更简单:

• 在第一阶段，您将构建一个数据结构，指示可以在字符串中嵌入单词的位置。这可以在 Θ(n^2) 时间内完成，假设您可以检查每个子字符串是否是分摊常数时间内的单词。

• 在第二阶段，您遍历此数据结构以输出单词组合列表。这可以在输出大小的线性时间内完成，Θ(r)。

所以总的来说，这个算法的时间复杂度为 Θ(n^2 + r)。

注意:为了形式上正确，您还应该考虑阅读英语单词列表所需的时间。如果您想考虑这一点，您可以引入一个额外的变量 d 并在时间复杂度中添加一个 + d 项。

此外:可以通过使用 Aho-Corasick algorithm 改进此绑定(bind)的 n^2 部分查找所有匹配的子字符串，而不是在哈希表中查找每个子字符串。