使用一個字符串分割 - 時間複雜度？

Question

要解決的問題：

給定一個非空字符串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。

這是正確的嗎？

Answer 1

我懷疑這個問題是回溯。如果單詞不能根據特定字典進行分割，或者如果有多個可能的具有共同前綴的子字符串會怎樣？例如，假設字典包含he,llenic和​​。如果將故障單的一個分支倒下，則需要回溯，並且時間複雜度會相應增加。

這類似於一個正則表達式匹配的問題：你給的例子是像對

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

檢測輸入字（任何數量的字典成員，以任意順序，沒有別的）。我不知道正則表達式匹配器的時間複雜性，但我知道回溯可以讓你進入serious time trouble。

我發現this answer它說：

運行鍼對一個字符串DFA的正則表達式編譯確實是爲O（n），但可能需要高達O（2^M）施工時間/空間（其中m =正則表達式大小）。

所以也許這是O（n^2），減少施工工作量。

Answer 2

你的榜樣的確會提出一個線性時間複雜度，但看看下面這個例子：

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

現在，第一個「地獄」的嘗試，但在接下來的遞歸循環，找不到解決方法（有沒有「o」），所以算法需要回溯，並假設「地獄」不適合（雙關語不打算），所以你嘗試「他」，並在下一級，你會發現「ll」，但它再次失敗，因爲沒有「o」。再次需要回溯。現在從「h」開始，然後是「e」，然後再次出現故障：您嘗試「ll」而沒有成功，所以回溯使用「l」代替：解決方案現在可用：「h e l lo」。

所以，沒有這個沒有O（n）時間複雜度。

Answer 3

讓我們開始將trie轉換爲nfa。我們在根上創建一個接受節點，並添加一個邊緣，該邊緣從trie中字典的每個單詞末尾移動到空字符的根節點。

時間複雜度：因爲在trie中的每一步我們只能移動到一個邊緣，代表輸入字符串和根中的當前字符。 （n）= 0×T（n-1）+ c 這就給我們O（2^n）

確實不是O（n），但是你可以用動態編程做得更好。

• 我們將使用自頂向下的方法。
• 在我們解決任何字符串問題之前，請檢查我們是否已經解決問題。
• 我們可以使用另一個HashMap來存儲已經解決的字符串的結果。
• 每當任何遞歸調用返回false時，將該字符串存儲在HashMap中。

這個想法是隻計算一次該詞的每個後綴。我們只有n個後綴，它會以O（n^2）結尾。

代碼形式algorithms.tutorialhorizo​​n.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是特里的長度。