Wörter mit Präfix zählen
Lektion 11 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Wie viele gespeicherte Wörter beginnen mit einem gegebenen Präfix? Gehen Sie nach dem Einfügen jedes Wortes von der Wurzel aus Zeichen für Zeichen entlang des Präfixes. Wenn ein Zeichen fehlt, ist die Antwort Null – kein Wort könnte möglicherweise mit diesem Präfix beginnen.
Wenn Sie das Ende des Präfixes erreichen, landen Sie auf einem Knoten. Jedes gespeicherte Wort, das mit diesem Präfix beginnt, befindet sich irgendwo in dem dort verwurzelten Teilbaum. Zählen Sie diese, indem Sie den Teilbaum durchlaufen und für jeden Knoten, bei dem isEndOfWord den Wert true hat, 1 addieren.
Aufgabe
EinfachSchreiben Sie eine Funktion countWordsWithPrefix, die ein String-Array words und einen String prefix erhält und die Anzahl der Wörter im Array zurückgibt, die mit dem angegebenen Präfix beginnen.
Ein leeres Präfix passt auf jedes Wort.
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"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
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