végre egy trie a insertsearch, és startsWith módszerekkel.
példa:
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
Megjegyzés:
- feltételezhetjük, hogy minden bemenet kisbetűk
a-z. - minden bemenet garantáltan nem üres karakterlánc.
Ez egy leetcode probléma:
megoldás:
mielőtt belemerülnénk a probléma megoldásába, először meg fogjuk érteni, hogy mi a Trie adatstruktúra röviden.
a Trie egy rendezett fa szerkezet, amelyet leginkább a String tárolására használnak. A karakterlánc tárolására azért használják, mert gyors visszakeresési ideje van. A karakterlánc megtalálásának bonyolultsága egy Trie-ben O(m), ahol m a karakterlánc hossza. Ha millió húrt tároltunk Trie-ben, és meg kell találnunk egy adott húrt, mondjuk cat, akkor a komplexitása O(3) lesz, nem csodálatos.
a kifejezés trie a szóból származik visszakeresés mivel nagyon egyszerűvé teszi egy karakterlánc visszakeresését a húrok gyűjteményéből. A Trie-t Előtagfának is nevezik.
a Trie-ben a gyökér üres, és minden gyermekcsomópont csak egy karaktert tartalmaz. Tehát egy adott csomópont gyermekcsomópontjainak száma az adott nyelv ábécéinek számától függ. Tegyük fel, hogy a trie-t használjuk az angol szavak tárolására, akkor minden csomópontnak 26 gyermekcsomópontja lesz.
a fenti képen csak 5 gyermekcsomópontot mutattunk be, de a tényleges gyökérben 26 gyermekcsomópont lesz, mindegyik ábécéhez egy.
most nézzük meg, hogy kell-e képviselnünk néhány karakterláncot a trie adatstruktúrában, akkor hogyan fog kinézni. Tegyük fel, hogy a labdát, a kopaszot, az autót, a macskát és a kutyát kell képviselnünk. Ez az alábbiak szerint fog kinézni. Az alábbi képen a narancssárga csomópontok a szó végét jelentik.
ez volt a bevezetés a trie-hez, de a fő rész az, hogy hogyan lehet megvalósítani a trie-t. Az alábbiakban megvizsgáljuk, hogyan lehet megvalósítani a Trie-t.
a Trie minden csomópontjának két információt kell tartalmaznia.
- logikai zászló, amely azt mondja, hogy ez a csomópont egy szó vége.
- 26 méretű tömb(a használt nyelvtől függ. 26 angol). A tömb minden indexe egy másik csomópontra mutat.
tegyük fel, hogy a Trie minden csomópontját TrieNode osztály képviseli. A TrieNode osztálynak két mezője lesz:
- isEnd: logikai mező.
- gyermek: TrieNode típusú tömb.
ezután lesz egy Trie osztályunk, amely tartalmazza az insert, search and startsWith metódust.
lássuk, hogyan fog működni a Beszúrás lépésről lépésre. Be kell helyeznünk a macskát a trie-be.
- kezdetben csak gyökércsomópontunk van. A tömb összes indexe null-t tartalmaz, az isEnd flag pedig szintén hamis.
2. Az első karaktert a cat i. e c. most a tömbben lévő index 2 lesz. Ha nem tudja, akkor megtaláljuk az index bármely ábécé tömb csinál char – ‘a’. Ezzel az a index értéke 0, b értéke 1, c értéke 2 és így tovább. A tömb 2-es indexéhez egy új csomópontot rendelünk hozzá.
3. Most áthelyezzük a mutatót a második csomópontra. A cat második ábécéje a. tehát inicializáljuk az indexet 0 új csomópontra.
4. A mutatót a következő csomópontra mozgatjuk. A cat következő ábécéje t. a T indexe 19. Mi inicializálja index 19 új csomópont.
5. A következő csomópontra lépünk . Most már nincs több ábécé, amelyet be kell illeszteni. Tehát ezt a csomópontot végként jelöljük meg.
az alábbiakban a beszúrási módszer Java kódja található.
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;
}
Az alábbiakban a teljes Java megoldás erre a programra a search and startsWith módszerrel.
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;
}
}