Zavést trie s insertsearchstartsWith metody.
Příklad:
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
Poznámka:
- můžete předpokládat, že všechny vstupy jsou tvořeny malými písmeny
a-z. - všechny vstupy jsou zaručeny jako neprázdné řetězce.
toto je problém leetcode:
řešení:
než se ponoříme do řešení tohoto problému, nejprve pochopíme, co je stručná Struktura dat Trie.
Trie je uspořádaná stromová struktura, která se většinou používá k ukládání řetězců. Důvod, proč se používá k ukládání řetězec je, že má rychlý čas načítání. Složitost nalezení řetězce v Trie je O (m), kde m je délka řetězce. Pokud jsme uložili milion řetězců v Trie a potřebujeme najít konkrétní řetězec, řekněme cat, pak jeho složitost bude O (3), není to úžasné.
termín trie pochází ze slova retrieval, protože velmi usnadňuje vyhledávání řetězce ze sbírky řetězců. Trie se také nazývá jako prefixový strom.
v Trie je kořen prázdný a každý podřízený uzel obsahuje pouze jeden znak. Počet podřízených uzlů, které může mít konkrétní uzel, tedy závisí na počtu abeced v daném jazyce. Předpokládejme, že používáme naše trie k ukládání anglických slov, pak každý uzel bude mít 26 podřízených uzlů.
Na obrázku výše jsme ukázali, pouze 5 dětí, ale ve skutečné root bude mít 26 podřízené uzly, jeden pro každý abecedy.
nyní se podívejme, jestli potřebujeme reprezentovat několik řetězců v datové struktuře trie, jak to bude vypadat. Předpokládejme, že potřebujeme reprezentovat míč, plešatý, auto, kočku a psa v trie. To bude vypadat, jak je uvedeno níže. Na obrázku níže oranžové uzly znamenají konec slova.
Toto byl úvod k tomu, co Trie je, ale hlavní na tom je, jak Trie může být realizován. Podíváme se, jak lze Trie implementovat níže.
každý uzel v Trie musí obsahovat dvě informace.
- booleovský příznak, který říká, že tento uzel je konec slova.
- pole velikosti 26 (záleží na použitém jazyce. 26 je pro angličtinu). Každý index v tomto poli ukazuje na jiný uzel.
řekněme, že každý uzel v Trie je reprezentován třídou Trienod. Třída Trienod bude mít dvě pole:
- isEnd: Boolean field.
- child: pole typu TrieNode.
pak budeme mít třídu Trie, která bude obsahovat metodu insert, search a startsWith.
podívejme se, jak bude insert fungovat krok za krokem. Musíme vložit kočku do našeho trie.
- zpočátku máme pouze kořenový uzel. Všechny indexy v jeho poli obsahuje null a isend příznak je také false.
2. Vybereme první znak z cat, tj. nyní bude index v poli 2. Pokud si nejste vědomi, pak najdeme index libovolné abecedy v poli tím, že uděláme char – ‚a‘. Tímto způsobem je index a 0, b je 1, c je 2 a tak dále. Jdeme na index 2 pole a přiřadí mu nový uzel.
3. Nyní přesuneme ukazatel na druhý uzel. Druhá abeceda v cat je a. takže inicializujeme index 0 na nový uzel.
4. Přesuneme ukazatel na další uzel. Další abeceda v cat je t.index t je 19. Inicializujeme index 19 do nového uzlu.
5. Přejdeme k dalšímu uzlu . Nyní již není možné vložit žádnou abecedu. Takže označíme tento uzel jako konec.
Níže je Java kód pro vložení metody.
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;
}
níže je kompletní Java řešení pro tento program s metodou vyhledávání a 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;
}
}