Zaczyna się od
Lekcja 7 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Cały sens istnienia drzew trie polega na szybkim odpowiadaniu na pytania o prefiksy. startsWith sprawdza, czy jakiekolwiek zapisane słowo zaczyna się od danego prefiksu — nie ma znaczenia, czy sam prefiks jest kompletnym wstawionym słowem.
Przechodzenie jest niemal identyczne jak w przypadku search: zaczynając od korzenia, podążaj za węzłami potomnymi, znak po znaku. Jeśli któregoś znaku brakuje po drodze, żadne zapisane słowo nie zaczyna się od tego prefiksu, więc zwróć false. Jeśli przejdziesz przez wszystkie znaki, nie zatrzymując się, odpowiedzią jest true — poddrzewo poniżej tego węzła zawiera co najmniej jedno zapisane słowo.
Jedyna różnica w porównaniu z search: na końcu nie ma sprawdzania isEndOfWord. Wystarczy dotrzeć do końca prefiksu.
Wyzwanie
ŁatwyDodaj metodę startsWith do klasy Trie.
Przyjmuje ciąg znaków prefix i zwraca:
true, jeśli jakieś wstawione słowo zaczyna się odprefix(prefiks może być całym słowem lub początkową częścią dłuższego słowa).falsew przeciwnym razie.
Spróbuj swoich sił
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
}
return 0;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
Poćwicz samodzielnie: Kompilator C online