Compter les mots avec un préfixe
Leçon 11 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Combien de mots stockés commencent par un préfixe donné ? Après avoir inséré chaque mot, parcourez l'arborescence à partir de la racine, un caractère à la fois, le long du préfixe. Si un caractère est manquant, la réponse est zéro - aucun mot ne peut commencer par ce préfixe.
Si vous atteignez la fin du préfixe, vous arrivez sur un nœud. Chaque mot stocké qui commence par ce préfixe se trouve quelque part dans le sous-arbre enraciné à cet endroit. Comptez-les en parcourant le sous-arbre et en ajoutant 1 pour chaque nœud où isEndOfWord est true.
Défi
FacileÉcrivez une fonction countWordsWithPrefix qui reçoit un tableau de chaînes de caractères words et une chaîne de caractères prefix, et renvoie le nombre de mots dans le tableau qui commencent par le préfixe donné.
Un préfixe vide correspond à tous les mots.
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"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
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