使用 trie 进行字符串分割 - 时间复杂度？

Question

待解决问题：

Given a non-empty string s and a string array wordArr containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given s = "leetcode", wordArr = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

在上面的问题中，构建一个每个字符串都在 wordArr 中的 trie 是否可行？然后，对于给定字符串 s 中的每个字符，沿着 trie 查找。如果 trie 分支终止，则此子字符串是完整的，因此将剩余的字符串传递到根并递归地执行完全相同的操作。

这应该是 O(N) 时间和 O(N) space 正确吗？我问是因为我正在处理的问题说这将是 O(N^2) 时间以最佳方式进行，我不确定我的方法有什么问题。

例如，如果s = "hello"和wordArr = ["he", "ll", "ee", "zz", "o"]，那么"he"将在trie的第一个分支完成，"llo"将向上传递到根递归地。然后，"ll" 将完成，因此 "o" 被传递到 trie 的根。那么"o"就完成了，也就是s的结束，所以return成立。如果 s 的末尾未完成，则 return 为假。

这是正确的吗？

Answer 1

我怀疑问题是回溯。如果该词不能根据特定词典进行分段怎么办，或者如果有多个可能的子串具有共同的前缀怎么办？例如，假设字典包含 he、llenic 和 llo。沿着 trie 的一个分支失败将需要回溯，时间复杂度会相应增加。

这类似于正则表达式匹配问题：您给出的示例就像是针对

测试输入词

^(he|ll|ee|zz|o)+$

（任意数量的字典成员，以任意顺序，仅此而已）。我不知道正则表达式匹配器的时间复杂度，但我知道回溯可以让你进入 serious time trouble.

我确实找到了 this answer 上面写着：

Running a DFA-compiled regular expression against a string is indeed O(n), but can require up to O(2^m) construction time/space (where m = regular expression size).

所以也许是 O(n^2) 减少了构建工作量。

Answer 2

你的例子确实表明线性时间复杂度，但看看这个例子：

 s = "hello" 
 wordArr = ["hell", "he", "e", "ll", "lo", "l", "h"]

现在先尝试"hell"，但是在下一个递归循环中，没有找到解（没有"o"），所以算法需要回溯假设"hell" 不合适（双关语不是故意的），所以你尝试 "he"，在下一个级别你找到 "ll"，但又失败了，因为没有 "o"。再次需要回溯。现在从 "h" 开始，然后是 "e"，然后再次失败：您尝试 "ll" 没有成功，所以回溯到使用 "l"：解决方案现在可用： "h e l lo".

所以，不，这没有 O(n) 时间复杂度。

Answer 3

让我们从将 trie 转换为 nfa 开始。我们在根上创建一个接受节点，并添加一条边，该边从 trie 中字典的每个单词末尾移动到空字符的根节点。

时间复杂度：由于 trie 中的每一步我们只能移动到代表输入字符串和根中的当前字符的一条边。 T(n) = 2×T(n-1)+c 这给了我们 O(2^n)

确实不是 O(n)，但是你可以使用动态规划做得更好。

我们将使用自上而下的方法。
在我们解决任何字符串之前检查我们是否已经解决了它。
我们可以使用另一个HashMap来存储已经解决的字符串的结果。
每当任何递归调用 returns 为假时，将该字符串存储在 HashMap 中。

想法是只计算单词的每个后缀一次。我们只有 n 个后缀，它将以 O(n^2) 结尾。

代码形式algorithms.tutorialhorizon.com:

Map<String, String> memoized;
Set<String> dict;

String SegmentString(String input) {
  if (dict.contains(input)) return input;
  if (memoized.containsKey(input) {
    return memoized.get(input);
  }
  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);
      String segSuffix = SegmentString(suffix);
      if (segSuffix != null) {
        memoized.put(input, prefix + " " + segSuffix);
        return prefix + " " + segSuffix;
    }
}

而且你可以做得更好！

Map<String, String> memoized;
Trie<String> dict;

String SegmentString(String input) 
{
    if (dict.contains(input)) 
        return input;
    if (memoized.containsKey(input) 
        return memoized.get(input);

    int len = input.length();
    foreach (StringBuilder word in dict.GetAll(input)) 
    {
        String prefix = input.substring(0, word.length);
        String suffix = input.substring(word.length, len);
        String segSuffix = SegmentString(suffix);
        if (segSuffix != null) 
        {
            memoized.put(input, word.ToString()  + " " + segSuffix);
            return prefix + " " + segSuffix;
        }
    }
    retrun null;
}

使用 Trieto 查找递归调用，只有当 Trie 到达单词结尾时，您将得到 o (z×n)，其中 z 是 Trie 的长度。

使用 trie 进行字符串分割 - 时间复杂度？

Using a trie for string segmentation - time complexity?

string

algorithm

substring

trie

time-complexity