string - 分词时间复杂度

Question

我遇到了这样的分词问题:

Given an input string and a dictionary of words,segment the input string into a space-separated sequence of dictionary words if possible.

例如，如果输入字符串是“applepie”并且字典包含一组标准的英语单词，那么我们将返回字符串“apple pie”作为输出

现在我自己想出了一个二次时间解决方案。我遇到了各种other quadratic time solutions using DP .

然而，在 Quora 中，一位用户发布了一个 linear time solution to this problem

我不知道它是如何变成线性的。他们在时间复杂度计算中有什么错误吗？此问题的最佳最坏情况时间复杂度是多少。我在这里发布最常见的 DP 解决方案

String SegmentString(String input, Set<String> dict) {
    int len = input.length();
    for (int i = 1; i < len; i++) {
        String prefix = input.substring(0, i);
        if (dict.contains(prefix)) {
              String suffix = input.substring(i, len);
              if (dict.contains(suffix)) {
                  return prefix + " " + suffix;
              }
        }
    }
    return null;
}

Answer 1

您认为的“线性”时间算法linked here工作原理如下:

如果字符串是sharperneedle并且字典是sharp, sharper, needle,

1. 它将 sharp 插入字符串。
2. 然后它发现 er 不在字典中，但如果我们将它与最后添加的单词组合，则 sharper 存在。因此它弹出最后一个元素并将其插入。

IMO 以上逻辑对于字符串 eaterror 和字典 eat, eater, error 是失败的。

这里 er 应该从列表中弹出 eat，然后压入 eater。剩余的字符串 ror 不应被识别和丢弃。

关于您发布的代码，如评论中所述，这仅适用于一个分区位置的两个单词。