implementera en trie med insertsearch och startsWith metoder.

exempel:

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

Obs:

• Du kan anta att alla ingångar består av små bokstäver a-z.
• alla ingångar är garanterade att vara icke-tomma strängar.

detta är ett leetcode-problem:

lösning:

innan vi dyker in i att lösa detta problem kommer vi först att förstå vilken Trie-datastruktur som är i korthet.

en Trie är en ordnad trädstruktur som oftast används för att lagra sträng. Anledningen till att den används för att lagra sträng är att den har snabb hämtningstid. Komplexiteten att hitta en sträng i en försök är O (m), där m är strängens längd. Om vi har lagrat en miljon strängar i Trie och vi måste hitta en viss sträng, låt oss säga katt då blir dess komplexitet O(3), är det inte fantastiskt.

termen trie kom från ordet hämtning eftersom det gör hämtning av en sträng från samlingen av strängar mycket lätt. Trie kallas också som Prefix träd.

i Trie är roten Tom och varje barnnod innehåller bara ett tecken. Så antalet barnnoder, en viss nod kan ha beror på antalet alfabet på ett visst språk. Antag att vi använder vår trie för att lagra engelska ord, då kommer varje nod att ha 26 barnnoder.

i bilden ovan har vi bara visat 5 barnnoder men i själva roten kommer att ha 26 barnnoder, en för varje alfabet.

nu, låt oss se om vi behöver representera några strängar i trie datastruktur så hur det kommer att se ut. Antag att vi må te representera boll, skallig, bil, katt och hund i trie. Detta kommer att se ut som visas nedan. I bilden nedan betyder de orange noderna slutet på ordet.

detta var introduktion till vad Trie är, men huvuddelen är hur trie kan implementeras. Vi kommer att se hur Trie kan genomföras nedan.

varje nod i Trie måste innehålla två bitar av information.

1. en boolesk flagga som säger att denna nod är slutet på ett ord.
2. en matris av storlek 26 (beror på vilket språk som används. 26 är för engelska). Varje index i denna array pekar på en annan nod.

låt oss säga att varje nod i Trie representeras av Trienodklass. Trienode-klassen kommer att ha två fält:

1. isEnd: booleskt fält.
2. barn: en array av typen TrieNode.

sedan kommer vi att ha en Trie-klass som innehåller insert, search och startsWith-metoden.

Låt oss se hur insert fungerar Steg för steg. Vi må te infoga katter i våra försök.

1. ursprungligen har vi bara rotnod. Alla index i dess array innehåller null och isend flagga är också falskt.

2. Vi väljer första tecknet från cat dvs c. nu index i array kommer att vara 2. Om du inte är medveten hittar vi indexet för något alfabet i array genom att göra char-’a’. Genom att göra detta är indexet för a 0, b är 1, c är 2 och så vidare. Vi går till index 2 av array och tilldelar den en ny nod.

3. Nu flyttar vi vår pekare till andra noden. Så vi initierar index 0 till ny nod.

4. Vi flyttar pekaren till nästa nod. Nästa alfabet i cat är t. indexet för t är 19. Vi initierar index 19 till ny nod.

5. Vi flyttar till nästa nod . Nu finns inget mer alfabet kvar att infogas. Så vi markerar denna nod som slut.

nedan är Java-koden för 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;
}

nedan är den kompletta Java-lösningen för detta program med Sök-och startsWith-metoden.

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;
}
}