Найти Минимальную длину подстроки Содержащую Все полученные строки

Question

Учитывая большой документ и короткий шаблон, состоящий из нескольких слов (например, 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; 
} 

Answer 1

Ваше решение O (N^2) временная сложность (в худшем случае, каждый суффикс а каждая проверка - O (n), потому что метод List.contains имеет линейную временную сложность). Более того, это неверно: ответ не всегда является суффиксом, он может быть любой подстрокой.

Более эффективное решение: перебирайте текст по слову и отслеживайте последнее вхождение каждого слова из шаблона (используя, например, хэш-таблицу). Обновите ответ после каждой итерации (подстрока-кандидат - от минимального последнего появления среди всех слов в шаблоне до текущей позиции). Это решение имеет линейную временную сложность (в предположении, что число слов в шаблоне является константой).