Autovervollständigung
Lektion 12 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Dies ist der klassische Anwendungsfall für einen Trie: Listen Sie basierend auf dem, was der Benutzer bisher eingegeben hat, jedes gespeicherte Wort auf, das mit diesem Präfix beginnt. Gehen Sie zum Präfix-Knoten; wenn dies nicht möglich ist, geben Sie nichts zurück. Erkunden Sie dann den darunter liegenden Teilbaum und sammeln Sie jedes Wort, das Sie finden.
Während Sie bei der DFS nach unten gehen, bauen Sie das Wort schrittweise auf, indem Sie das Zeichen der Kante anhängen, die Sie gerade überquert haben. Jedes Mal, wenn Sie auf einen Knoten stoßen, bei dem isEndOfWord den Wert true hat, ist der aktuelle Pfad einer der Treffer.
Aufgabe
MittelSchreiben Sie eine Funktion autocomplete, die ein String-Array words und einen String prefix erhält und die Liste der Wörter aus dem Array zurückgibt, die mit prefix beginnen.
Die zurückgegebene Liste muss in aufsteigender (alphabetischer) Reihenfolge vorliegen. Wenn kein Wort übereinstimmt, geben Sie eine leere Liste zurück.
Sie müssen die Klasse Trie verwenden (bereitgestellt in trie zusammen mit trienode) - verwenden Sie keine in der Sprache eingebauten Funktionen wie Sets, Dicts oder Maps zum Zählen/Verfolgen.
Probier es selbst
#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;
}
Alle Lektionen in Tries - Datenstrukturen-Serie #8
3Übungsaufgaben
Längster gemeinsamer PräfixWörter mit Präfix zählenAutovervollständigungLängstes Wort im WörterbuchWort-Segmentierung