Najdłuższe słowo w słowniku
Lekcja 13 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Mając słownik wyrazów, znajdź najdłuższy wyraz, który można zbudować po jednym znaku naraz, dopisując znaki do wyrazu, który już znajduje się w słowniku. "world" liczy się tylko wtedy, gdy "w", "wo", "wor" i "worl" również są zapisanymi wyrazami.
To idealne zastosowanie drzewa trie. Wstaw każdy wyraz, a następnie wykonaj DFS od korzenia — schodź do dziecka tylko wtedy, gdy jest ono oznaczone jako isEndOfWord. Dzięki temu każdy węzeł odwiedzony podczas DFS reprezentuje ścieżkę, na której każdy prefiks jest samodzielnym wyrazem.
Śledź najdłuższą ścieżkę. Jeśli dwie ścieżki mają tę samą długość, wybierz leksykograficznie mniejszą.
Wyzwanie
ŚredniNapisz funkcję longestWordInDict, która przyjmuje tablicę ciągów znaków words i zwraca najdłuższe słowo, które można utworzyć przez dodawanie po jednym znaku do krótszego słowa z tej tablicy.
Jeśli dwa słowa mają taką samą długość, zwróć to wcześniejsze leksykograficznie. Jeśli tablica jest pusta, zwróć pusty ciąg znaków.
Musisz użyć klasy Trie (dostępnej w trie wraz z trienode) — nie używaj wbudowanych w język struktur, takich jak zbiory, słowniki ani mapy, do zliczania lub śledzenia elementów.
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 = longestWordInDict(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