给定一个大文档和一个由几个单词组成的短模式（例如W1 W2 W3），找到具有所有顺序的所有单词的最短字符串（例如W2 foo bar dog W1 cat W3-是有效模式）
我将“大文档”构造为字符串列表。我相信我的解决方案是O（nlog（n）），但是我不确定（我也不知道它是否正确）。有没有更快的方法？请注意，下面是伪编码的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;
}
您的解决方案具有O（n ^ 2）时间复杂度（在最坏的情况下，每个后缀都被检查，并且每个检查都为O（n），因为List.contains方法具有线性时间复杂度）。而且，这是不正确的：答案并不总是后缀，它可以是任何子串。
一种更有效的解决方案：逐字遍历您的文本，并跟踪模式中每个单词的最后一次出现（例如，使用哈希表）。每次迭代后更新答案（候选子字符串是从模式中所有单词中最小的最后出现到当前位置的子字符串）。该解决方案具有线性时间复杂度（假设模式中的单词数为常数）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句