Policz słowa z danym prefiksem
Lekcja 11 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Ile zapisanych słów zaczyna się od danego prefiksu? Po wstawieniu każdego słowa przejdź od korzenia, znak po znaku, wzdłuż prefiksu. Jeśli brakuje któregokolwiek znaku, odpowiedź wynosi zero — żadne słowo nie może zaczynać się od tego prefiksu.
Jeśli dotrzesz do końca prefiksu, znajdziesz się w węźle. Każde zapisane słowo zaczynające się od tego prefiksu znajduje się gdzieś w poddrzewie zakorzenionym w tym węźle. Policz je, przechodząc przez poddrzewo i dodając 1 za każdy węzeł, w którym isEndOfWord ma wartość true.
Wyzwanie
ŁatwyNapisz funkcję countWordsWithPrefix, która przyjmuje tablicę ciągów znaków words i ciąg znaków prefix, a następnie zwraca liczbę słów w tablicy, które zaczynają się od podanego prefiksu.
Pusty prefiks pasuje do każdego słowa.
Musisz użyć klasy Trie (dostępnej w trie wraz z trienode) — nie używaj wbudowanych w język konstrukcji, 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 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;
}
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