字休息的時間複雜度

我碰到這是這樣的話突破問題就來了：字休息的時間複雜度

給定的輸入字符串和單詞的字典，段輸入串入字典單詞空格分隔的序列如果可能。

例如，如果輸入字符串爲「applepie」和字典有一組標準的英語單詞，那麼我們將返回字符串「蘋果派」作爲輸出

現在我自己想出了一個二次時間解決方案。我碰到各種各樣的other quadratic time solutions using DP。

但是在Quora的用戶發佈一個linear time solution to this problem

我無法弄清楚它是如何出來是線性的。他們在時間複雜性計算中有一些錯誤嗎？什麼是最好的最壞情況時間複雜度這個問題。我張貼在這裏最常見的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; 
}

來源

2013-12-16 Abhiroop Sarkar

應該如何解決歧義？ 'expertsexchange => [expert，sex，change]，[experts，exchange]' – mishadoff

線性時間解決方案僅適用於兩個單詞的情況。你對此有什麼要求？最簡單的通用解決方案涉及生成2^n個項目的冪集，DP可以使其更快至O（n^2）。 –

顯然另一個線性定時算法可以在這個鏈接上找到http://stackoverflow.com/questions/8793387/how-to-break-down-a-given-text-into-words-from-the-dictionary?rq= 1看第二個答案 –

你linked here作品如下的「線性」時間算法：

如果字符串爲sharperneedle和字典是sharp, sharper, needle，

它在字符串中推入sharp。
然後它看到er不在字典中，但是如果我們將它與添加的最後一個字相結合，則存在sharper。因此，它彈出的最後元件和推動此英寸

IMO上述邏輯字符串eaterror和字典eat, eater, error失敗。

這裏er應該從列表中彈出來，並推入eater。剩餘的字符串ror不得被識別和丟棄。

至於你發佈的代碼，正如評論中提到的，這隻適用於兩個單詞分區的地方。

來源

2013-12-16 09:18:52

@ Erti-ChrisEelmaa該算法的描述是按照鏈接http://www.quora.com/Programming-Interviews/Write-a-program-that-breaks-up-a-string字母不帶空格的字符串與適當的空間，例如ip peanutbutter-op-peanut-butter/answer/Gaurav-Mishra-29由OP給出，而不是代碼發佈。 –

字休息的時間複雜度

回答

相關問題