Najdłuższy wspólny prefiks
Lekcja 10 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Kolejne wyzwania zostały zaprojektowane tak, aby wykorzystać w nich Trie.
Użyj klas Trie i TrieNode, które utworzyłeś w poprzednich lekcjach (znajdziesz je w plikach po lewej). Do każdego wyzwania dołączony jest nowy plik solution, w którym napiszesz funkcję korzystającą z Trie.
Pierwszy problem: mając listę słów, znajdź najdłuższy wspólny prefiks, który występuje we wszystkich. Po wstawieniu każdego słowa do drzewa trie odpowiedzią jest ścieżka od korzenia w dół, która biegnie tak długo, jak na każdym kroku istnieje dokładnie jedno dziecko i żaden węzeł nie oznacza końca słowa.
Wyzwanie
ŁatwyNapisz funkcję longestCommonPrefix, która otrzymuje tablicę ciągów znaków words i zwraca najdłuższy ciąg znaków będący prefiksem każdego słowa w tablicy.
Jeśli tablica jest pusta lub nie istnieje wspólny prefiks, zwróć pusty ciąg znaków.
Musisz użyć klasy Trie (udostępnionej w trie wraz z trienode) — nie używaj wbudowanych w język struktur, takich jak zbiory, słowniki czy mapy, do zliczania ani śledzenia.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
3Wyzwania praktyczne
Najdłuższy wspólny prefiksPolicz słowa z danym prefiksemAutouzupełnianieNajdłuższe słowo w słownikuDzielenie słowaPoćwicz samodzielnie: Kompilator C online