Autocomplétion
Leçon 12 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
C'est le cas d'utilisation classique d'un trie : étant donné ce que l'utilisateur a saisi jusqu'à présent, listez chaque mot stocké qui commence par ce préfixe. Parcourez jusqu'au nœud du préfixe ; si vous ne le pouvez pas, ne retournez rien. Ensuite, explorez le sous-arbre en dessous et collectez chaque mot que vous trouvez.
Pendant que vous descendez lors du DFS, construisez le mot de manière incrémentielle en ajoutant le caractère de l'arête que vous venez de traverser. Chaque fois que vous atteignez un nœud où isEndOfWord est true, le chemin actuel est l'une des correspondances.
Défi
MoyenÉcrivez une fonction autocomplete qui reçoit un tableau de chaînes de caractères words et une chaîne de caractères prefix, et renvoie la liste des mots du tableau qui commencent par prefix.
La liste renvoyée doit être dans l'ordre croissant (alphabétique). Si aucun mot ne correspond, renvoyez une liste vide.
Vous devez utiliser la classe Trie (fournie dans trie avec trienode) - n'utilisez pas les fonctions intégrées du langage comme les ensembles (sets), les dictionnaires (dicts) ou les maps pour compter ou suivre les éléments.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}
Toutes les leçons de Tries - Série Structures de données n°8
3Défis d'entraînement
Plus long préfixe communCompter les mots avec un préfixeAutocomplétionPlus long mot du dictionnaireDécomposition de mots