zaimplementuj trie za pomocąinsertsearch IstartsWith metod.
przykład:
Trie trie = new Trie();trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Uwaga:
- można założyć, że wszystkie wejścia składają się z małych liter
a-z. - wszystkie wejścia są gwarantowane jako niepuste ciągi.
jest to problem z kodem Leet:
rozwiązanie:
zanim zajmiemy się rozwiązaniem tego problemu, najpierw zrozumiemy, czym jest struktura danych Trie w skrócie.
Trie jest uporządkowaną strukturą drzewa, która jest najczęściej używana do przechowywania ciągów znaków. Powodem, dla którego jest używany do przechowywania ciągów jest to, że ma szybki czas pobierania. Złożoność znalezienia ciągu w Trie wynosi O (M), gdzie M jest długością ciągu. Jeśli przechowaliśmy w Trie milion ciągów i musimy znaleźć konkretny ciąg, powiedzmy cat, to jego złożoność będzie O (3), czyż nie jest zdumiewająca.
termin trie pochodzi od słowa retrieval, ponieważ sprawia, że pobieranie łańcucha z kolekcji łańcuchów jest bardzo łatwe. Trie jest również nazywany jako drzewo Prefiksowe.
w Trie root jest pusty, a każdy węzeł potomny zawiera tylko jeden znak. Liczba węzłów potomnych, które dany węzeł może mieć, zależy od liczby alfabetów w danym języku. Załóżmy, że używamy naszego trie do przechowywania angielskich słów, wtedy każdy węzeł będzie miał 26 węzłów potomnych.
na powyższym obrazku pokazaliśmy tylko 5 węzłów potomnych, ale w rzeczywistości root będzie miał 26 węzłów potomnych, po jednym dla każdego alfabetu.
teraz zobaczmy, czy musimy reprezentować kilka łańcuchów w strukturze danych trie, a następnie jak to będzie wyglądać. Załóżmy, że musimy reprezentować piłkę, łysego, samochód, kota i psa w trie. Będzie to wyglądać jak pokazano poniżej. Na poniższym obrazku pomarańczowe węzły oznaczają koniec słowa.
to było wprowadzenie do tego, czym jest Trie, ale główną częścią jest sposób implementacji trie. Poniżej przyjrzymy się, w jaki sposób można wdrożyć Trie.
każdy węzeł w Trie musi zawierać dwie informacje.
- znacznik logiczny, który mówi, że ten węzeł jest końcem słowa.
- tablica wielkości 26 (zależy od używanego języka. 26 jest dla języka angielskiego). Każdy indeks w tej tablicy wskazuje na inny węzeł.
powiedzmy, że każdy węzeł w Trie jest reprezentowany przez klasę TrieNode. Klasa TrieNode będzie miała dwa pola:
- isend: pole logiczne.
- child: tablica typu TrieNode.
wtedy będziemy mieli klasę Trie, która będzie zawierać metodę insert, search i startsWith.
zobaczmy, jak będzie działać insert krok po kroku. Musimy włożyć kota do naszego trie.
- początkowo mamy tylko węzeł główny. Wszystkie indeksy w tablicy zawierają null, a znacznik isEnd jest również false.
2. Wybieramy pierwszy znak z kat. np. teraz indeks w tablicy będzie wynosił 2. Jeśli nie jesteś świadomy, to znajdujemy indeks dowolnego alfabetu w tablicy wykonując znak – 'a’. W ten sposób indeks a wynosi 0, b wynosi 1, c wynosi 2 i tak dalej. Przechodzimy do indeksu 2 tablicy i przypisujemy jej nowy węzeł.
3. Teraz przenosimy nasz wskaźnik do drugiego węzła. Drugi alfabet w cat to a. więc inicjujemy indeks 0 do nowego węzła.
4. Przenosimy wskaźnik do następnego węzła. Następny alfabet w kocie to t. indeks t wynosi 19. Inicjujemy indeks 19 do nowego węzła.
5. Przechodzimy do następnego węzła . Teraz nie ma już alfabetu do wstawienia. Oznaczamy ten węzeł jako koniec.
poniżej znajduje się kod Javy dla metody insert.
public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}
poniżej znajduje się kompletne rozwiązanie Java dla tego programu z metodą search and startsWith.
class Trie {
class TrieNode {
static final int ALPHABET_SIZE = 26;
TrieNode child = new TrieNode; boolean isEnd;
}
TrieNode root;
/**
* Initialize your data structure here.
*/
public Trie() {
root = new TrieNode();
}
/**
* Inserts a word into the trie.
*/
public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
if (tempNode != null && tempNode.isEnd == false) {
return false;
}
return true;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
return true;
}
}