Le plus court extrait de chaînes contenant une liste de mots

Question

Je travaille sur ce problème sur google foobar. "Ecrivez une fonction appelée answer (document, searchTerms) qui renvoie l'extrait le plus court du document, contenant tous les termes de recherche donnés, les termes de recherche peuvent apparaître dans n'importe quel ordre." La longueur d'un extrait est le nombre de mots dans l'extrait

Ma solution échoue sur 2 cas de test (ils ne vous disent pas lequel) et je ne suis pas sûr de ce que je fais mal. J'ai testé des dizaines de scénarios différents et cela fonctionne sur chacun d'entre eux.

Tous les mots du document sont séparés par des espaces, il y a au moins un terme de recherche et au moins un mot dans le document. Les termes de recherche sont distincts et sont garantis d'apparaître au moins une fois dans le document.

Si plusieurs extraits sont les plus courts, renvoyez le premier extrait.

par exemple: réponse ("foo foo bar très foo bar", { "foo", "bar"}) réponse est "bar foo"

Je l'ai regardé d'autres postes et a trouvé des algorithmes similaires, est le mien est différent? method to find the shortest substring containing the given words:optimization required

public static String answer(String document, String[] searchTerms) { 
    String[] doc = document.split(" "); 
    int docLength = doc.length; 

    int termsTotal = searchTerms.length; 

    Map<String, Integer> searchTermsMap = new HashMap<>(); 

    for (int i = 0; i < docLength; i++) { 
     String word = doc[i]; 

     if (containsSearchTerm(word, searchTerms)) { 
      searchTermsMap.put(word, i); 

      if (searchTermsMap.size() == termsTotal) { 
       int max = 0; 
       int min = Integer.MAX_VALUE; 

       for (Integer value : searchTermsMap.values()) { 
        max = Math.max(max, value); 
        min = Math.min(min, value); 
       } 

       if (max - min < currentLast - currentStart) { 
        currentStart = min; 
        currentLast = max; 
       } 
      } 
     } 
    } 

    StringBuilder result = new StringBuilder(); 
    result.append(doc[currentStart]); 
    for (int i = currentStart + 1; i <= currentLast; i++) { 
     result.append(" ").append(doc[i]); 
    } 

    return result.toString(); 
} 

private static boolean containsSearchTerm(String word, String[] searchTerms) { 
    for (String term : searchTerms) 
     if (word.equals(term)) 
      return true; 
    return false; 
} 

Answer 1

J'ai trouvé ce problème sur certains sites web, comme je suis arrivé est petit problème au lieu de dire substring extrait.

Si ce n'est pas un problème, alors le seul problème que je vois est currentStart et currentFinish valeurs que vous n'initialisez pas réponse de la fonction. Essayez de leur assigner des valeurs dans cette fonction.