Längster gemeinsamer Präfix
Lektion 10 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Die nächsten Herausforderungen sind darauf ausgelegt, einen Trie zu verwenden.
Verwenden Sie die Trie- und TrieNode-Klassen, die Sie in den vorherigen Lektionen erstellt haben (diese werden Ihnen in den Dateien auf der linken Seite zur Verfügung gestellt). Jede Herausforderung liefert Ihnen eine neue solution-Datei, in der Sie eine Funktion schreiben, die den Trie verwendet.
Unser erstes Problem: Finden Sie bei einer gegebenen Liste von Wörtern das längste gemeinsame Präfix, das sie alle teilen. Nachdem jedes Wort in einen Trie eingefügt wurde, ist die Antwort der Pfad von der Wurzel abwärts, solange bei jedem Schritt genau ein Kind existiert und kein Knoten das Ende eines Wortes markiert.
Aufgabe
EinfachSchreiben Sie eine Funktion longestCommonPrefix, die ein String-Array words erhält und den längsten String zurückgibt, der ein Präfix jedes Wortes im Array ist.
Wenn das Array leer ist oder kein gemeinsames Präfix existiert, 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 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 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;
}
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