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

-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

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

回答

相关问题