Implementer en trie med insertsearch ogstartsWith 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

Merk:

• du kan anta at alle innganger består av små bokstaver a-z.
• Alle innganger er garantert å være ikke-tomme strenger.

Dette er en leetcode problem:

Løsning:

Før vi dykke inn løse dette problemet, vil vi først forstå Hva Trie datastruktur er i korte trekk.

En Trie er en ordnet trestruktur som hovedsakelig brukes til å lagre Streng. Grunnen til at Den brukes til å lagre Streng er at den har rask gjenfinningstid. Kompleksiteten ved å finne En Streng i En Trie Er O (m) , hvor m er lengden på strengen. Hvis vi har lagret en million strenger I Trie, og vi må finne en bestemt streng, la oss si cat da dens kompleksitet vil Være O (3), er det ikke fantastisk.

begrepet trie kom fra ordet henting som det gjør henting av en streng fra samlingen av strenger veldig enkelt. Trie kalles også Som Prefiks Treet.

i Trie er roten tom, og hver undernode inneholder bare ett tegn. Så antall barnnoder, en bestemt node kan ha, avhenger av antall alfabeter på et gitt språk. Anta at vi bruker vår trie til å lagre engelske ord, da vil hver node ha 26 barnnoder.

i bildet ovenfor har vi bare vist 5 barnnoder, men i selve roten vil det ha 26 barnnoder, en for hvert alfabet.Nå, la Oss se Om vi trenger å representere noen strenger i trie datastruktur så hvordan det vil se ut. Anta at vi må representere ball, skallet, bil, katt og hund i trie. Dette vil se ut som vist nedenfor. I bildet nedenfor betyr oransje noder slutten av ordet.

dette var introduksjon til hva trie er, men hoveddelen er hvordan trie kan implementeres. Vi vil se hvordan Trie kan implementeres nedenfor.

hver node I Trie må inneholde to opplysninger.

1. et boolsk flagg som forteller at denne noden er slutten på et ord.
2. en matrise av størrelse 26 (avhenger av språket som brukes. 26 er for engelsk). Hver indeks i denne matrisen peker til en annen node.

La oss si at hver node I Trie er representert Av TrieNode-klassen. TrieNode-klassen vil ha to felt:

1. isEnd: Boolsk felt.
2. barn: en matrise Av Typen TrieNode.

da vil vi ha En Trie klasse som vil inneholde innsats, søk og startsWith metode.

La oss se hvordan insert vil fungere trinnvis. Vi må sette inn katt i vår trie.

1. I Utgangspunktet har Vi bare rotnode. Alle indeksene i arrayet inneholder null og isEnd-flagget er også falskt.

2. Vi velger første tegn fra cat dvs. c. nå indeksen i array vil være 2. Hvis du ikke er klar, finner vi indeksen for et alfabet i array ved å gjøre char – ‘a’. Ved å gjøre dette er indeksen for a 0, b er 1, c er 2 og så videre. Vi går til indeks 2 av array og tildeler den en ny node.

3. Nå flytter vi pekeren til andre node. Så vi initialiserer indeks 0 til ny node.

4. Vi flytter pekeren til neste node. Det neste alfabetet i cat er t. indeksen for t er 19. Vi initialiserer indeks 19 til ny node.

5. Vi flytter til neste node . Nå er det ikke mer alfabet igjen å bli satt inn. Så vi markerer denne noden som slutt.

nedenfor er java-koden for insert-metoden.

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øsningen for dette programmet med søk og startsmed 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;
}
}