查找最小長度子字符串包含所有的字符串

-1

給定一個大文件，包括了幾句（例如，W1，W2，W3）一個空頭格局，發現有任何爲了所有單詞的最短字符串（例如W2 foo bar dog W1 cat W3 - 是一種有效模式）查找最小長度子字符串包含所有的字符串

我將「大文檔」構造爲一個字符串列表。我相信我的解決方案是O（nlog（n）），但我不確定（我也不確定它是否正確）。有更快的方法嗎？請注意，下面pseudocoded Java，所以顯然不會編譯，但我相信信息是明確的：

main(){ 
    List<String> wordsToCheckFor; 
    List<String> allWords; 
    int allWordsLength = allWords.length; 
    int minStringLength = POS_INFINITY; 
    List<String> minString; 

    //The idea here is to divide and conquer the string; I will first 
    //check the entire string, then the entire string minus the first 
    //word, then the entire string minus the first two words, and so on... 

    for(int x = 0; x < allWordsLength; x++){ 
     if(checkString(allWords, wordsToCheckFor) && (allWords.length < minStringLength)){ 
      minString = allWords; 
      minStringLength = allWords.length(); 
     } 
     allWords.remove(0); 
    } 

    System.out.println(minString);   
} 


checkString(List<String> allWords, List<String> wordsToCheckFor){ 
    boolean good = true; 
    foreach(String word : wordsToCheckFor){ 
     if(!allWords.contains(word)) 
      good = false; 
    } 
    return good; 
}

來源

2014-11-14 John Roberts

這至少是O（n * n）。你正在調用List.contains（這是O（n））n次。這也是不正確的。如果模式位於字符串的開頭，它將不起作用。例如：'W1 W2 W3 a b c' – 2014-11-14 23:56:45

您的解決方案已爲O（n^2）的時間複雜度（在最壞的情況下，每個後綴檢查，並且每個檢查是O（n），因爲List.contains方法具有線性時間複雜度）。此外，這是不正確的：答案並不總是後綴，它可以是任何子字符串。

更有效的解決方案：逐字地遍歷文本，並跟蹤模式中每個單詞的最後出現位置（例如，使用散列表）。在每次迭代後更新答案（候選子字符串是從模式中的所有單詞到當前位置的最後發生的最小次數）。該解決方案具有線性時間複雜度（假設模式中的字數是常數）。

來源

2014-11-14 23:58:36 kraskevich

查找最小長度子字符串包含所有的字符串

回答

相關問題