使用一个字符串分割 - 时间复杂度？

要解决的问题：使用一个字符串分割 - 时间复杂度？

给定一个非空字符串s和一个字符串数组wordArr含有的非空字列表，确定是否s时，可以分割成一个的空格分隔序列或更多的词典单词。您可能假定字典不包含重复的单词。例如，给定s =“leetcode”，wordArr = [“leet”，“code”]。

返回true，因为“leetcode”可以分段为“leet code”。

在上面的问题，它会工作建立一个trie，每个字符串在wordArr。然后，对于给定字符串s中的每个字符，按照特里字母排序。如果一个trie分支终止，那么这个子字符串是完整的，因此将剩余的字符串传递给根，并递归地完成同样的事情。

这应该是O（N）时间和O（N）空间是否正确？我问，因为我正在处理的问题说这将是最佳方式的O（N^2）时间，我不知道我的方法有什么问题。

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

这是正确的吗？

来源

2017-02-28 Sunny

如果'wordArr'不包含不相交的单词，可能会涉及回溯。假设'wordArr = [“lee”，“leet”，“code”]'。你会首先匹配'lee'，然后浪费很多时间去寻找'tcode'的匹配项。 – chepner

我怀疑这个问题是回溯。如果单词不能根据特定字典进行分割，或者如果有多个可能的具有共同前缀的子字符串会怎样？例如，假设字典包含he,llenic和。如果将故障单的一个分支倒下，则需要回溯，并且时间复杂度会相应增加。

这类似于一个正则表达式匹配的问题：你给的例子是像对

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

检测输入字（任何数量的字典成员，以任意顺序，没有别的）。我不知道正则表达式匹配器的时间复杂性，但我知道回溯可以让你进入serious time trouble。

我发现this answer它说：

运行针对一个字符串DFA的正则表达式编译确实是为O（n），但可能需要高达O（2^M）施工时间/空间（其中m =正则表达式大小）。

所以也许这是O（n^2），减少施工工作量。

来源

2017-02-28 17:59:52 cxw

在trie中回溯的时间复杂度是多少？我在分析时遇到了麻烦。 – Sunny

@Sunny你超出了我的CS理论知识范围，我很抱歉地说！ :)我猜想你会得到像* O（n log m）*这样的字符串长度* n *和深度* m *，但这只是一个猜测。我通过特里搜索（日志时间，如果特里平衡适中或者如果可以将其转换为BST）在每个字符位置得到这个结果。我会说检查链接的其他答案中提到的NFA算法。祝你好运！ – cxw

你的榜样的确会提出一个线性时间复杂度，但看看下面这个例子：

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

现在，第一个“地狱”的尝试，但在接下来的递归循环，找不到解决方法（有没有“o”），所以算法需要回溯，并假设“地狱”不适合（双关语不打算），所以你尝试“他”，并在下一级，你会发现“ll”，但它再次失败，因为没有“o”。再次需要回溯。现在从“h”开始，然后是“e”，然后再次出现故障：您尝试“ll”而没有成功，所以回溯使用“l”代替：解决方案现在可用：“h e l lo”。

所以，没有这个没有O（n）时间复杂度。

来源

2017-02-28 18:01:57 trincot

我在cxw的答案上写了这个，但回溯部分的时间复杂度是多少？ – Sunny

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

时间复杂度：因为在trie中的每一步我们只能移动到一个边缘，代表输入字符串和根中的当前字符。（n）= 0×T（n-1）+ c 这就给我们O（2^n）

确实不是O（n），但是你可以用动态编程做得更好。

我们将使用自顶向下的方法。
在我们解决任何字符串问题之前，请检查我们是否已经解决问题。
我们可以使用另一个HashMap来存储已经解决的字符串的结果。
每当任何递归调用返回false时，将该字符串存储在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找到递归调用，只有当特里达到一个字结束时，你会得到ø（Z×n）其中z是特里的长度。

来源

2017-03-01 22:26:31 Dolev

使用一个字符串分割 - 时间复杂度？

回答

相关问题