Implementer en trie med insertsearch og startsWith metoder.
eksempel:
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
Bemærk:
- du kan antage, at alle indgange består af små bogstaver
a-z. - alle indgange er garanteret at være ikke-tomme strenge.
Dette er et leetcode-problem:
løsning:
før vi dykker ned i at løse dette problem, vil vi først forstå, hvad Trie datastruktur er kort.
en Trie er en ordnet træstruktur, der for det meste bruges til at gemme streng. Grunden til det bruges til at gemme streng er, at det har hurtig hentning tid. Kompleksiteten ved at finde en streng i en Trie er O(m), hvor m er længden af strengen. Hvis vi har gemt en million strenge i Trie, og vi er nødt til at finde en bestemt streng, lad os sige kat, så vil dens kompleksitet være O(3), er det ikke fantastisk.
udtrykket trie kom fra ordet hentning, da det gør hentning af en streng fra samlingen af strenge meget let. Trie kaldes også som præfiks træ.
i Trie er roden Tom, og hver barneknude indeholder kun et tegn. Så antallet af underordnede noder, en bestemt knude kan have, afhænger af antallet af alfabeter på et givet sprog. Antag, at vi bruger vores trie til at gemme engelske ord, så vil hver node have 26 barneknuder.
i ovenstående billede har vi kun vist 5 barneknuder, men i den faktiske rod vil der være 26 barneknuder, en for hvert alfabet.
lad os nu se, om vi har brug for at repræsentere få strenge i trie datastruktur, så hvordan det vil se ud. Antag, at vi er nødt til at repræsentere kugler, skaldede, biler, katte og hunde i Trier. Dette vil se ud som vist nedenfor. I nedenstående billede betyder de orange noder slutningen af ordet.
dette var introduktion til, hvad Trie er, men hoveddelen er, hvordan trie kan implementeres. Vi vil se, hvordan Trie kan implementeres nedenfor.
hver node i Trie skal indeholde to stykker information.
- et boolsk flag, der fortæller, at denne knude er slutningen af et ord.
- et array af størrelse 26 (afhænger af det anvendte sprog. 26 er for engelsk). Hvert indeks i dette array peger på en anden knude.
lad os sige, at hver node i Trie er repræsenteret af TrieNode klasse. TrieNode-klassen har to felter:
- isEnd: boolsk felt.
- barn: en række Type TrieNode.
derefter har vi en Trie-klasse, der indeholder indsæt, søg og startmed metode.
lad os se, hvordan indsatsen fungerer trin for trin. Vi er nødt til at indsætte katte i vore trie.
- oprindeligt har vi kun rodknude. Alle indekser i sit array indeholder null og isEnd flag er også falsk.
2. Vi vælger første tegn fra kat dvs c. nu indekset i array vil være 2. Hvis du ikke er opmærksom, finder vi indekset for ethvert alfabet i array ved at gøre char-‘a’. Ved at gøre dette er indekset for a 0, b er 1, c er 2 og så videre. Vi går til indeks 2 af array og tildeler det en ny node.
3. Nu flytter vi vores peger til anden node. Så vi initialiserer indeks 0 til ny node.
4. Vi flytter markøren til næste node. Det næste alfabet i cat er t.indekset for t er 19. Vi initialiserer indeks 19 til ny node.
5. Vi flytter til næste node . Nu er der ikke mere alfabet tilbage at indsætte. Så vi markerer denne knude som ende.
nedenfor er Java-koden til Indsæt metode.
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;
}
nedenfor er den komplette Java-løsning til dette program med søgning og startermed metode.
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;
}
}