单词拆分的时间复杂度

Question

单词拆分的时间复杂度

stringalgorithmdata-structuresdictionarytime-complexity

3

我遇到了一个称为“断词问题”的编程难题，大意如下：

给定一个输入字符串和一个单词字典，如果可能的话将输入字符串分割成以空格分隔的一系列单词。

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

我自己想出了一个二次时间复杂度的解决方案。我还发现了各种使用DP的其他二次时间复杂度的解决方案。

然而，在Quora上，有一个用户发布了一个线性时间复杂度的解决方案。

我无法理解它如何成为线性的。时间复杂度计算中有错误吗？这个问题的最坏情况时间复杂度是什么？我在此发布最常见的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;
}

- Abhiroop Sarkar

1

歧义应该如何解决？expertsexchange => [expert, sex, change], [experts, exchange] - mishadoff

线性时间解决方案仅适用于两个单词的情况。您对此有什么要求？最简单的通用解决方案涉及生成2^n个项目的幂集，DP可以将其加速到O(n^2)。 - Thomas Jungblut

显然在此链接中可以找到另一个线性时间算法：https://dev59.com/1moy5IYBdhLWcg3wEJ9n?rq=1 请看第二个答案。 - Abhiroop Sarkar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Bansal · Answer 1

你在这里链接的“线性”时间算法如下：

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

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

我认为上述逻辑对于字符串eaterror和字典eat, eater, error无效。

在这里，er将从列表中弹出eat，并推入eater。剩余的字符串ror将不被识别并且被丢弃。

关于您发布的代码，正如评论中所提到的，它仅适用于具有一个分区位置的两个单词。