Algoritmo LeetCode: implementazione di Trie (albero dei prefissi) c

2024-07-12

原题链接🔗：Implementare Trie (albero dei prefissi)
difficoltà: Medio⭐️⭐️

argomento

Trie (pronunciato come "provare") o albero dei prefissi È una struttura di dati ad albero utilizzata per archiviare e recuperare in modo efficiente le chiavi in un set di dati di tipo stringa. Questa struttura dati ha diversi casi d'uso, come il completamento automatico e il controllo ortografico.

Si prega di implementare la classe Trie:

Trie() Inizializza l'oggetto dell'albero dei prefissi.
void insert(String word) Inserisci la stringa nell'albero dei prefissiword 。
boolean search(String word) se stringaword Nell'albero dei prefissi, return true(vale a dire, è stato inserito prima del recupero); altrimenti, restituisce false 。
boolean startsWith(String prefix) Se la stringa è stata inserita in precedenza wordUno dei prefissi è prefix ,ritorno true ; Altrimenti, ritornafalse。

Esempio:

accedere
[“Trie”, “inserisci”, “cerca”, “cerca”, “iniziaCon”, “inserisci”, “cerca”]
[[], [“mela”], [“mela”], [“app”], [“app”], [“app”]]
produzione
[nullo, nullo, vero, falso, vero, nullo, vero]

spiegare
Trie trie = nuovo Trie();
trie.insert(“mela”);
trie.search("mela"); // Restituisce Vero
trie.search("app"); // Restituisce False
trie.startsWith("app"); // Restituisce Vero
trie.insert(“app”);
trie.search("app"); // Restituisce Vero

suggerimento:

1 <= lunghezza parola, lunghezza prefisso <= 2000
la parola e il prefisso sono costituiti solo da lettere inglesi minuscole
Il numero totale di chiamate di inserimento, ricerca e avvioCon non supera 3 * 10⁴ Di second'ordine

albero dei prefissi

Un albero di prefissi, noto anche come albero Trie (pronunciato "try"), è una struttura dati utilizzata per archiviare raccolte di stringhe, che consente il recupero e l'inserimento rapidi di stringhe, nonché query per i prefissi di stringa. Ciascun nodo dell'albero dei prefissi rappresenta un prefisso di una stringa e i figli di ciascun nodo rappresentano tutte le possibili estensioni del prefisso che aggiungono un carattere.

Caratteristiche degli alberi dei prefissi：
efficienza dello spazio: per le raccolte di stringhe con un numero elevato di prefissi comuni, gli alberi di prefisso possono risparmiare spazio di archiviazione.
efficienza temporale: La complessità temporale delle operazioni di inserimento e ricerca è solitamente O(m), dove m è la lunghezza della stringa.
raccolta dinamica: l'albero dei prefissi può inserire ed eliminare dinamicamente stringhe, il che è adatto per scenari che richiedono aggiornamenti frequenti.

Operazioni di base degli alberi dei prefissi：
inserire: Inserisci una stringa nell'albero, partendo dal nodo radice e scendendo carattere per carattere. Se il nodo figlio corrispondente al carattere non esiste, crea un nuovo nodo.
ricerca: Cerca se esiste una stringa nell'albero, partendo dal nodo radice e scendendo carattere per carattere. Se il nodo figlio di un carattere non esiste, la ricerca fallisce.
Ricerca del prefisso: Controlla se c'è qualche stringa preceduta da una certa stringa, simile all'operazione di ricerca, ma non è necessario controllare il flag di fine dell'ultimo nodo.
eliminare: L'eliminazione di una stringa da un albero richiede l'eliminazione ricorsiva dei nodi garantendo al tempo stesso che i nodi con prefisso comune di altre stringhe non vengano eliminati.

Scenari applicativi dell'albero dei prefissi：
completamento automatico: nei motori di ricerca o negli editor di testo, fornisce rapidamente suggerimenti di completamento in base ai prefissi immessi dall'utente.
Controllo ortografico: controlla se la parola inserita dall'utente è stata digitata correttamente e fornisce suggerimenti ortografici corretti.
Instradamento IP: In una rete, per determinare il percorso di instradamento di un pacchetto viene utilizzata la corrispondenza del prefisso più lungo.
Analisi della sequenza genica: In bioinformatica, utilizzato per abbinare e recuperare rapidamente sequenze di geni.

risposta

Idee per la risoluzione dei problemi：

Un Trie (albero del prefisso) è una struttura dati ad albero utilizzata per il recupero rapido delle chiavi in un set di dati di stringa. È un tipo speciale di albero in cui ogni nodo rappresenta un carattere e il percorso dalla radice al nodo rappresenta una stringa. Gli alberi trie vengono spesso utilizzati per implementare funzioni come il completamento automatico e il controllo ortografico.

Di seguito sono riportati i passaggi fondamentali e le idee per la risoluzione dei problemi per l'implementazione di un albero Trie:

Definire i nodi Trie：

Ogni nodo Trie solitamente contiene un insieme di caratteri o un valore booleano per rappresentare la fine della parola e puntatori ai nodi figli.

Inizializza Trie：

Crea un nodo radice che non contenga caratteri ma serva da punto di partenza per tutte le parole.

operazione di inserimento：

Partendo dal nodo radice, per ogni carattere della stringa da inserire:
Se il nodo figlio corrispondente al personaggio non esiste, crea un nuovo nodo figlio.
Sposta il nodo corrente sul nodo figlio corrispondente.

Operazione di ricerca：

Partendo dal nodo radice, per ogni carattere della stringa che vuoi cercare:
Se esiste il nodo figlio corrispondente al carattere, continua la ricerca.
Se non esiste, viene restituito un errore di ricerca.

Ricerca del prefisso：

Simile all'operazione di ricerca, ma si preoccupa solo dell'esistenza del prefisso della stringa.

Elimina operazione(opzionale):

Implementare la possibilità di eliminare le parole secondo necessità, che in genere comporta l'eliminazione dei nodi e richiede la gestione del conteggio dei riferimenti del nodo.

Funzione di completamento automatico(opzionale):

Dato un prefisso, restituisce tutte le stringhe che iniziano con quel prefisso.

dimostrazione c++：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

Risultato dell'output:

1
0
1

Codice indirizzo magazzino：prova

Condivisione della tecnologia