Plus long préfixe commun
Leçon 10 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Les prochains défis sont conçus pour utiliser un Trie.
Utilisez les classes Trie et TrieNode que vous avez construites dans les leçons précédentes (elles sont fournies pour vous dans les fichiers sur la gauche). Chaque défi vous livre un nouveau fichier solution où vous écrivez une fonction qui UTILISE le Trie.
Notre premier problème : étant donné une liste de mots, trouvez le plus long préfixe commun qu'ils partagent tous. Après avoir inséré chaque mot dans un trie, la réponse est le chemin depuis la racine vers le bas tant qu'il existe exactement un enfant à chaque étape et qu'aucun nœud n'est une fin de mot.
Défi
FacileÉcrivez une fonction longestCommonPrefix qui reçoit un tableau de chaînes de caractères words et renvoie la plus longue chaîne qui est un préfixe de chaque mot du tableau.
Si le tableau est vide, ou si aucun préfixe commun n'existe, 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, les dictionnaires 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 = longestCommonPrefix(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