断字时间复杂度

Question

我遇到了单词中断问题，它是这样的：

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

然而，在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;
}

Answer 1

您在这里链接的“线性”时间算法的工作方式如下：

如果字符串为SharperNeedle，而dictionary为Sharp,sharper,Needle，

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

对于字符串eaterror和字典eat,eater,error，上述逻辑失败。

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

关于您发布的代码，正如注释中提到的，这只适用于一个分区位置的两个单词。