Plus long mot du dictionnaire
Leçon 13 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Étant donné un dictionnaire de mots, trouvez le mot le plus long qui peut être construit un caractère à la fois en l'ajoutant à un mot déjà présent dans le dictionnaire. "world" ne compte que si "w", "wo", "wor" et "worl" sont également des mots enregistrés.
C'est un cas d'utilisation parfait pour un trie. Insérez chaque mot, puis effectuez un DFS à partir de la racine - mais ne descendez vers un enfant que s'il est marqué isEndOfWord. De cette façon, chaque nœud que nous visitons pendant le DFS représente un chemin où chaque préfixe est lui-même un mot.
Suivez le chemin le plus long. Si deux chemins ont la même longueur, choisissez celui qui est lexicographiquement le plus petit.
Défi
MoyenÉcrivez une fonction longestWordInDict qui reçoit un tableau de chaînes de caractères words et renvoie le mot le plus long pouvant être construit en ajoutant un caractère à la fois à un mot plus court présent dans le tableau.
Si deux mots ont la même longueur, renvoyez celui qui est le plus petit dans l'ordre lexicographique. Si le tableau est vide, renvoyez une chaîne 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 line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", 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