Implementieren Sie einen Trie mit insertsearch und startsWith Methoden.

Beispiel:

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

Hinweis:

• Sie können davon ausgehen, dass alle Eingaben aus Kleinbuchstaben bestehen a-z.
• Alle Eingaben sind garantiert nicht leere Zeichenfolgen.

Dies ist ein Leetcode-Problem:

Lösung:

Bevor wir uns mit der Lösung dieses Problems befassen, werden wir zunächst verstehen, was die Trie-Datenstruktur in Kürze ist.

Ein Trie ist eine geordnete Baumstruktur, die hauptsächlich zum Speichern von Zeichenfolgen verwendet wird. Der Grund, warum es zum Speichern von Zeichenfolgen verwendet wird, ist die schnelle Abrufzeit. Die Komplexität des Auffindens einer Zeichenfolge in einem Versuch ist O (m), wobei m die Länge der Zeichenfolge ist. Wenn wir eine Million Zeichenfolgen in Trie gespeichert haben und eine bestimmte Zeichenfolge finden müssen, sagen wir cat, dann ist ihre Komplexität O (3), ist das nicht erstaunlich.

Der Begriff trie stammt vom Wort retrieval ab, da er das Abrufen einer Zeichenfolge aus der Sammlung von Zeichenfolgen sehr einfach macht. Trie wird auch als Präfixbaum bezeichnet.

In Trie ist die Wurzel leer und jeder untergeordnete Knoten enthält nur ein Zeichen. Die Anzahl der untergeordneten Knoten, die ein bestimmter Knoten haben kann, hängt also von der Anzahl der Alphabete in einer bestimmten Sprache ab. Angenommen, wir verwenden unseren Versuch, englische Wörter zu speichern, dann hat jeder Knoten 26 untergeordnete Knoten.

Im obigen Bild haben wir nur 5 untergeordnete Knoten gezeigt tatsächlich hat root jedoch 26 untergeordnete Knoten, einen für jedes Alphabet.

Nun wollen wir sehen, ob wir einige Zeichenfolgen in der Trie-Datenstruktur darstellen müssen, dann wie es aussehen wird. Angenommen, wir müssen Ball, Glatze, Auto, Katze und Hund in Trie darstellen. Dies wird wie unten gezeigt aussehen. Im folgenden Bild bedeutet der orangefarbene Knoten das Ende des Wortes.

Dies war eine Einführung in das, was Trie ist, aber der Hauptteil ist, wie Trie implementiert werden kann. Wir werden sehen, wie Trie unten implementiert werden kann.

Jeder Knoten in Trie muss zwei Informationen enthalten.

1. Ein boolesches Flag, das angibt, dass dieser Knoten das Ende eines Wortes ist.
2. Ein Array der Größe 26(abhängig von der verwendeten Sprache. 26 für Englisch). Jeder Index in diesem Array zeigt auf einen anderen Knoten.

Angenommen, jeder Knoten in Trie wird durch die TrieNode-Klasse dargestellt. Die TrieNode-Klasse wird zwei Felder haben:

1. isEnd: Boolean field.
2. child: Ein Array vom Typ TrieNode.

Dann haben wir eine Trie-Klasse, die die Methoden insert , search und startsWith enthält.

Mal sehen, wie insert Schritt für Schritt funktioniert. Wir müssen cat in unseren Versuch einfügen.

1. Anfangs haben wir nur Wurzelknoten. Alle Indizes in seinem Array enthalten null und das isEnd Flag ist ebenfalls false .

2. Wir wählen das erste Zeichen aus cat dh jetzt ist der Index im Array 2. Wenn Sie sich dessen nicht bewusst sind, finden wir den Index eines Alphabets im Array, indem wir char-‚a‘ . Auf diese Weise ist der Index von a 0, b 1, c 2 und so weiter. Wir gehen zum Index 2 des Arrays und weisen ihm einen neuen Knoten zu.

3. Jetzt bewegen wir unseren Zeiger auf den zweiten Knoten. Das zweite Alphabet in cat ist a. Also initialisieren wir den Index 0 auf einen neuen Knoten.

4. Wir bewegen den Zeiger zum nächsten Knoten. Das nächste Alphabet in cat ist t. Der Index von t ist 19. Wir initialisieren Index 19 auf neuen Knoten.

5. Wir bewegen uns zum nächsten Knoten . Nun muss kein Alphabet mehr eingefügt werden. Also markieren wir diesen Knoten als Ende.

Unten ist der Java-Code für die Insert-Methode.

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

Nachfolgend finden Sie die vollständige Java-Lösung für dieses Programm mit der Methode search und 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;
}
}