string - 使用 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) 空间正确吗？我问是因为我正在处理的问题说这将是 O(N^2) 时间以最佳方式进行，我不确定我的方法有什么问题。

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

这是正确的吗？

Answer 1

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

 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) 时间复杂度。