Algorithme LeetCode : implémentation de Trie (arbre de préfixes) c

2024-07-12

原题链接🔗：Implémenter Trie (arbre de préfixes)
difficulté: Moyen⭐️⭐️

sujet

Trie (prononcé comme « essayer ») ou arbre de préfixes Est une structure de données arborescente utilisée pour stocker et récupérer efficacement des clés dans un ensemble de données de chaîne. Cette structure de données a de nombreux cas d'utilisation, tels que la saisie semi-automatique et la vérification orthographique.

Veuillez implémenter la classe Trie :

Trie() Initialisez l'objet d'arborescence de préfixes.
void insert(String word) Insérer une chaîne dans l'arborescence des préfixesword 。
boolean search(String word) si chaîneword Dans l'arborescence des préfixes, retournez true(c'est-à-dire, a été inséré avant la récupération, sinon, renvoie) ; false 。
boolean startsWith(String prefix) Si la chaîne a été insérée avant wordL'un des préfixes est prefix ,retour true ; Sinon, retournezfalse。

Exemple:

entrer
[« Trie », « insérer », « rechercher », « rechercher », « commencePar », « insérer », « rechercher »]
[[], [« pomme »], [« pomme »], [« appli »], [« appli »], [« appli »], [« appli »]]
sortir
[null, nul, vrai, faux, vrai, nul, vrai]

expliquer
Trie trie = nouveau Trie();
trie.insert(“pomme”);
trie.search("pomme"); // Renvoie Vrai
trie.search("app"); // Retourne False
trie.startsWith("app"); // Renvoie True
trie.insert(“application”);
trie.search("app"); // Renvoie True

indice:

1 <= longueur du mot, longueur du préfixe <= 2000
le mot et le préfixe sont constitués uniquement de lettres anglaises minuscules
Le nombre total d'appels d'insertion, de recherche et de démarrage avec ne dépasse pas 3 * 10⁴ De second ordre

arbre de préfixes

Un arbre de préfixes, également connu sous le nom d'arbre de Trie (prononcé « try »), est une structure de données utilisée pour stocker des collections de chaînes, qui permet une récupération et une insertion rapides de chaînes, ainsi que des requêtes pour les préfixes de chaînes. Chaque nœud de l'arborescence des préfixes représente un préfixe d'une chaîne, et les enfants de chaque nœud représentent toutes les extensions possibles du préfixe qui ajoutent un caractère.

Caractéristiques des arbres de préfixes：
efficacité de l'espace: Pour les collections de chaînes avec un grand nombre de préfixes communs, les arborescences de préfixes peuvent économiser de l'espace de stockage.
l'efficacité du temps: La complexité temporelle des opérations d'insertion et de recherche est généralement O(m), où m est la longueur de la chaîne.
collection dynamique: L'arborescence des préfixes peut insérer et supprimer dynamiquement des chaînes, ce qui convient aux scénarios nécessitant des mises à jour fréquentes.

Opérations de base des arbres de préfixes：
insérer: Insérez une chaîne dans l'arborescence, en partant du nœud racine et en descendant caractère par caractère. Si le nœud enfant correspondant au caractère n'existe pas, créez un nouveau nœud.
recherche: Rechercher si une chaîne existe dans l'arborescence, en commençant par le nœud racine et en descendant caractère par caractère. Si le nœud enfant d'un caractère n'existe pas, la recherche échoue.
Recherche de préfixe: Vérifie s'il existe une chaîne préfixée par une certaine chaîne, similaire à l'opération de recherche, mais n'a pas besoin de vérifier l'indicateur de fin du dernier nœud.
supprimer: Supprimer une chaîne d'un arbre nécessite de supprimer des nœuds de manière récursive tout en garantissant que les nœuds de préfixe commun des autres chaînes ne sont pas supprimés.

Scénarios d'application de l'arborescence des préfixes：
Saisie automatique: Dans les moteurs de recherche ou les éditeurs de texte, proposez rapidement des suggestions de complétion basées sur les préfixes saisis par l'utilisateur.
Vérification orthographique: Vérifie si le mot saisi par l'utilisateur est correctement orthographié et fournit des suggestions orthographiques correctes.
Routage IP: Dans un réseau, la correspondance de préfixe la plus longue est utilisée pour déterminer le chemin de routage d'un paquet.
Analyse de séquence génétique: En bioinformatique, utilisé pour faire correspondre et récupérer rapidement des séquences de gènes.

répondre

Idées de résolution de problèmes：

Un Trie (arbre de préfixes) est une structure de données arborescente utilisée pour la récupération rapide des clés dans un ensemble de données de chaîne. Il s'agit d'un type particulier d'arbre dans lequel chaque nœud représente un caractère et le chemin allant de la racine à un nœud représente une chaîne. Les arbres Trie sont souvent utilisés pour implémenter des fonctions telles que la complétion automatique et la vérification orthographique.

Voici les étapes de base et les idées de résolution de problèmes pour la mise en œuvre d'un arbre de Trie :

Définir les nœuds Trie：

Chaque nœud Trie contient généralement un ensemble de caractères ou une valeur booléenne pour représenter la fin du mot, ainsi que des pointeurs vers des nœuds enfants.

Initialiser le test：

Créez un nœud racine qui ne contient aucun caractère mais sert de point de départ à tous les mots.

opération d'insertion：

En partant du nœud racine, pour chaque caractère de la chaîne à insérer :
Si le nœud enfant correspondant au personnage n'existe pas, créez un nouveau nœud enfant.
Déplacez le nœud actuel vers le nœud enfant correspondant.

Opération de recherche：

En partant du nœud racine, pour chaque caractère de la chaîne que vous souhaitez rechercher :
Si le nœud enfant correspondant au personnage existe, poursuivez la recherche.
S'il n'existe pas, un échec de recherche est renvoyé.

Recherche de préfixe：

Similaire à l'opération de recherche, mais ne se soucie que de savoir si le préfixe de la chaîne existe.

Opération de suppression(facultatif):

Implémentez la possibilité de supprimer des mots selon les besoins, ce qui implique généralement la suppression de nœuds et nécessite la gestion du nombre de références du nœud.

Fonction de saisie semi-automatique(facultatif):

Étant donné un préfixe, renvoie toutes les chaînes commençant par ce préfixe.

démonstration 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

Résultat de sortie :

1
0
1

Adresse de l'entrepôt de codes：Trier

Partage de technologie