Längstes Wort im Wörterbuch
Lektion 13 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Gegeben ist ein Wörterbuch mit Wörtern. Finden Sie das längste Wort, das Zeichen für Zeichen aufgebaut werden kann, indem es an ein bereits im Wörterbuch vorhandenes Wort angehängt wird. "world" zählt nur, wenn alle von "w", "wo", "wor" und "worl" ebenfalls gespeicherte Wörter sind.
Dies eignet sich hervorragend für einen Trie. Fügen Sie jedes Wort ein und führen Sie dann eine Tiefensuche (DFS) von der Wurzel aus durch – aber steigen Sie nur in einen Kindknoten ab, wenn dieser als isEndOfWord markiert ist. Auf diese Weise stellt jeder Knoten, den wir während der DFS besuchen, einen Pfad dar, bei dem jedes Präfix selbst ein Wort ist.
Verfolgen Sie den längsten Pfad. Wenn zwei Pfade die gleiche Länge haben, wählen Sie den lexikographisch kleineren.
Aufgabe
MittelSchreiben Sie eine Funktion longestWordInDict, die ein String-Array words erhält und das längste Wort zurückgibt, das durch das schrittweise Anhängen einzelner Zeichen an ein kürzeres Wort im Array gebildet werden kann.
Wenn zwei Wörter die gleiche Länge haben, geben Sie das lexikografisch kleinere zurück. Wenn das Array leer ist, geben Sie einen leeren String zurück.
Sie müssen die Klasse Trie verwenden (bereitgestellt in trie zusammen mit trienode) - verwenden Sie keine in der Sprache integrierten Strukturen wie Sets, Dicts oder Maps zum Zählen oder Verfolgen.
Probier es selbst
#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;
}
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