Implementa un trie coninsertsearch estartsWith metodi.

Esempio:

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

Nota:

• Si può supporre che tutti gli input siano costituiti da lettere minuscolea-z.
• Tutti gli input sono garantiti per essere stringhe non vuote.

Questo è un problema leetcode:

Solution:

Prima di immergerci nella risoluzione di questo problema, prima capiremo quale struttura dei dati Trie è in breve.

Un Trie è una struttura ad albero ordinata che viene principalmente utilizzata per memorizzare stringhe. Il motivo per cui viene utilizzato per memorizzare la stringa è che ha un tempo di recupero rapido. La complessità di trovare una stringa in un Trie è O (m), dove m è la lunghezza della stringa. Se abbiamo memorizzato un milione di stringhe in Trie e abbiamo bisogno di trovare una stringa particolare, diciamo che cat allora la sua complessità sarà O(3), non è sorprendente.

Il termine trie deriva dalla parola recupero in quanto rende molto facile il recupero di una stringa dalla raccolta di stringhe. Trie è anche chiamato come albero prefisso.

In Trie la radice è vuota e ogni nodo figlio contiene solo un carattere. Quindi il numero di nodi figlio, un particolare nodo può avere dipende dal numero di alfabeti in una determinata lingua. Supponiamo che stiamo usando il nostro trie per memorizzare le parole inglesi, quindi ogni nodo avrà 26 nodi figlio.

Nell’immagine sopra abbiamo dimostrato solo 5 nodi figlio, ma nel reale principale dispone di 26 nodi figli, uno per ogni alfabeto.

Ora, vediamo se abbiamo bisogno di rappresentare poche stringhe nella struttura dei dati di trie, quindi come apparirà. Supponiamo che abbiamo bisogno di rappresentare palla, calvo, auto, gatto e cane in trie. Questo apparirà come mostrato di seguito. Nell’immagine qui sotto, i nodi arancioni significa fine della parola.

Questo è avvenuto con l’introduzione a quello che Trie è, ma la parte principale è come Trie può essere implementato. Vedremo come Trie può essere implementato di seguito.

Ogni nodo in Trie deve contenere due informazioni.

1. Un flag booleano che indica che questo nodo è la fine di una parola.
2. Un array di dimensioni 26 (dipende dalla lingua utilizzata. 26 è per l’inglese). Ogni indice in questo array punta a un altro nodo.

Diciamo che ogni nodo in Trie è rappresentato dalla classe TrieNode. La classe TrieNode avrà due campi:

1. isEnd: campo booleano.
2. child: Un array di tipo TrieNode.

Quindi, avremo una classe Trie che conterrà il metodo insert, search e startsWith.

Vediamo come insert funzionerà passo dopo passo. Dobbiamo inserire cat nel nostro trie.

1. Inizialmente abbiamo solo nodo radice. Tutti gli indici nel suo array contiene null e isEnd flag è anche false.

2. Scegliamo il primo carattere da cat cioè Ora l’indice nell’array sarà 2. Se non sei a conoscenza, troviamo l’indice di qualsiasi alfabeto in array facendo char-’a’. In questo modo l’indice di a è 0, b è 1, c è 2 e così via. Andiamo all’indice 2 dell’array e gli assegniamo un nuovo nodo.

3. Ora spostiamo il nostro puntatore al secondo nodo. Il secondo alfabeto in cat è a. Quindi inizializziamo l’indice 0 al nuovo nodo.

4. Spostiamo il puntatore al nodo successivo. Il prossimo alfabeto in cat è t. L’indice di t è 19. Inizializziamo l’indice 19 al nuovo nodo.

5. Passiamo al nodo successivo . Ora non più alfabeto è lasciato da inserire. Quindi contrassegniamo questo nodo come fine.

di Seguito è il codice Java per il metodo di inserimento.

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

Di seguito è riportata la soluzione Java completa per questo programma con il metodo search e 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;
}
}