Implement Trie (Prefix Tree)

+10

Un trie, ou arbre préfixe, stocke les mots de manière à répondre rapidement aux questions sur leur début. Construis-en un pour des mots en minuscules avec trois opérations : insert w ajoute le mot w, search w indique si w a été inséré lui-même, et startsWith p indique si un mot inséré commence par p. Un mot est considéré comme un préfixe de lui-même.

Tu reçois les opérations dans l’ordre dans ops, et words[i] est le mot ou le préfixe correspondant à ops[i]. Exécute-les sur un même trie initialement vide et renvoie une chaîne par opération : "null" pour une insertion, et "true" ou "false" pour une recherche ou un startsWith.

Fonction

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: les opérations, dans l’ordre où elles s’exécutent
wordsstring-array: le mot ou le préfixe de chaque opération
Renvoiestring-array: une réponse par opération, sous forme de texte

Contraintes

1 ≤ ops.length ≤ 2000
words.length == ops.length
Chaque ops[i] est insert, search ou startsWith.
1 ≤ words[i].length ≤ 20
words[i] contient uniquement des lettres minuscules anglaises.

Exemples

Entrée: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Sortie: ["null", "false", "true", "null", "true"]
Explication: Seul card est stocké au départ, donc rechercher car renvoie "false" : il n’a jamais été inséré comme mot. C’est le début de card, donc startsWith car renvoie "true". Une fois que car est inséré, la recherche le trouve.

Entrée: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Sortie: ["null", "null", "true", "false", "false", "true", "true"]
Explication: Les deux mots commencent par te, donc startsWith te vaut "true", mais aucun mot n'est exactement te, donc la recherche échoue. Aucun mot ne commence par tex. ten a été inséré, et tea est un préfixe de lui-même, donc les deux dernières réponses sont "true".

Entrée: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Sortie: ["false", "false", "null", "true", "false", "true"]
Explication: Le trie est vide au départ, donc les deux premières réponses sont "false". Après l’insertion de dog, la recherche le trouve, aucun mot ne commence par dogs, et do est le début de dog.

+16 tests cachés à la soumission

Pour aller plus loin

Comment ajouteriez-vous une opération countPrefix p qui renvoie combien de mots stockés distincts commencent par p, toujours en temps O(L) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un ensemble de hachage répond instantanément à search, mais startsWith pose une question sur chaque mot qui commence d’une certaine manière, et un ensemble n’a aucune notion de début. Un trie stocke les débuts eux-mêmes : chaque mot est un chemin de lettres depuis la racine, les mots qui commencent de la même façon partagent le début de leur chemin, et un indicateur sur un nœud marque la fin d’un mot stocké. Les deux questions nécessitent alors un seul parcours d’au plus L liens, où L est la longueur de la requête, quel que soit le nombre de mots stockés.

Gardez une liste de mots et parcourez-la

Intuition

Conservez chaque mot inséré dans une liste. Pour search w, comparez w avec chaque mot enregistré. Pour startsWith p, vérifiez si un mot enregistré commence par p. Dans le deuxième exemple, startsWith te examine d’abord tea et s’arrête là ; startsWith tex doit examiner les deux mots avant de répondre "false".

C’est correct, et avec les limites fixées ici, cela se termine, mais chaque requête nécessite de parcourir tous les mots enregistrés. Avec n mots enregistrés, une requête coûte jusqu’à n comparaisons de jusqu’à L lettres chacune. 1 000 mots enregistrés et 1 000 requêtes représentent un million de comparaisons de chaînes, et le travail continue d’augmenter avec le dictionnaire. Rien n’est partagé non plus : tea et ten stockent chacun leur propre t et e.

Algorithme

Commencez avec une liste de mots vide.
Pour insert w : ajoutez w à la liste.
Pour search w : renvoyez si un mot stocké est égal à w.
Pour startsWith p : renvoyez si un mot stocké commence par p.
Enregistrez chaque réponse sous forme de texte et renvoyez la liste.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Un trie : liens vers les enfants et indicateur de fin

Intuition

Chaque nœud d’un trie représente un préfixe : les lettres sur le chemin depuis la racine jusqu’à ce nœud. La racine représente le préfixe vide. Un nœud contient deux choses : un lien enfant pour chaque lettre pouvant suivre (un tableau de 26 emplacements, ou une map associant une lettre à un nœud) et un indicateur, isEnd, qui précise si un mot stocké se termine exactement à ce nœud.

insert parcourt le mot depuis la racine. Pour chaque lettre, il suit le lien enfant, en créant d’abord le nœud si le lien est absent ; à la dernière lettre, il active isEnd. Dans le deuxième exemple, l’insertion de tea crée les nœuds pour t, te et tea, puis marque tea. L’insertion de ten réutilise t et te et ajoute uniquement ten. Les deux mots partagent le chemin correspondant à te, d’où le nom d’arbre de préfixes.

search et startsWith effectuent le même parcours sans rien créer. Si un lien est absent, aucun mot stocké ne commence par ces lettres, donc les deux renvoient false : tex s’arrête au nœud correspondant à te, qui n’a pas de lien x. Si le parcours atteint la fin, le nœud où il se trouve correspond au préfixe recherché. startsWith renvoie true, et search renvoie la valeur de l’indicateur de ce nœud. Le nœud correspondant à te existe, mais son indicateur est désactivé, car les mots qui le traversent se terminent plus bas. Donc startsWith te renvoie true et search te renvoie false.

L’indicateur permet de distinguer un mot d’un préfixe. Dans le premier exemple, après l’insertion de card, le chemin c, a, r existe. Sans l’indicateur, search car renverrait true à tort. L’insertion ultérieure de car ne crée aucun nœud ; elle active seulement l’indicateur.

Chaque opération suit au plus L liens, où L est la longueur du mot ; elle coûte donc O(L), quel que soit le nombre de mots stockés. Le trie contient un nœud par préfixe distinct, et jamais plus de nœuds que le nombre total de lettres insérées.

Algorithme

Définis un nœud avec des liens vers ses enfants (26 emplacements ou une map) et un indicateur isEnd, puis crée une racine vide.
Pour insert w : à partir de la racine, suis le lien correspondant à chaque lettre de w, en créant le nœud lorsque le lien est absent. Définis isEnd sur le dernier nœud.
Écris une fonction auxiliaire find(p) : à partir de la racine, suis le lien correspondant à chaque lettre de p, et arrête-toi dès qu’un lien est absent. Renvoie le nœud atteint.
Pour search w : réponds vrai lorsque find(w) atteint un nœud dont l’indicateur isEnd est défini.
Pour startsWith p : réponds vrai lorsque find(p) atteint un nœud.
Exécute les opérations dans l’ordre et note "null", "true" ou "false" pour chacune.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Pièges et cas limites

La plupart des bugs viennent de la confusion entre « un mot se termine ici » et « un mot passe par ici ».

Laisser search répondre true dès que le chemin existe. Après avoir inséré card, le chemin pour car existe, mais car n’a jamais été inséré.
Définir isEnd uniquement sur les nœuds nouvellement créés. Insérer card après cards ne crée rien, mais le dernier nœud a quand même besoin de son indicateur.
Créer un nouvel enfant même lorsque le lien existe déjà. Cela coupe tout ce qui est stocké en dessous : insérer ten avec un nouveau nœud t fait perdre tea.
Oublier qu’un mot est un préfixe de lui-même. Après avoir inséré tea, startsWith tea est true.
Lire au-delà de la fin du chemin. Un préfixe plus long que tous les mots, comme sunny lorsque seul sun est stocké, doit s’arrêter au premier lien manquant et répondre false.
Renvoyer des booléens ou omettre les insertions de la réponse. Chaque opération produit une chaîne, y compris "null" pour une insertion.

Questions fréquentes4

Quelle est la complexité temporelle d’un trie ?

L’insertion, la recherche et startsWith suivent chacune un lien par lettre de leur argument. Elles prennent donc un temps de O(L) pour un mot de longueur L, indépendamment du nombre de mots stockés. Le trie contient au plus un nœud par lettre insérée ; l’espace requis est donc de O(T) nœuds pour T lettres insérées au total, et chaque nœud stocke jusqu’à 26 liens vers des enfants.

Pourquoi utiliser un trie plutôt qu’un ensemble de hachage ?

Un ensemble de hachage répond aux recherches de mots entiers en O(L), mais ne peut pas répondre à une recherche de préfixe sans parcourir chaque mot. Tu pourrais ajouter un deuxième ensemble contenant chaque préfixe de chaque mot, mais un mot de 20 lettres stockerait alors 20 préfixes totalisant 210 lettres. Un trie stocke chaque préfixe partagé une seule fois et répond aux deux questions en parcourant les mêmes nœuds. Avec 26 emplacements de tableau par nœud, le parcours sous un préfixe rencontre également les mots dans l’ordre alphabétique, ce dont la saisie semi-automatique a besoin.

Un nœud de trie doit-il utiliser un tableau de 26 liens ou une table de hachage ?

Un tableau offre la recherche d’enfant la plus rapide, avec un index par lettre, mais chaque nœud réserve 26 emplacements même s’il n’en utilise qu’un. Une map ne stocke que les enfants existants et fonctionne avec n’importe quel alphabet, au prix d’une étape de hachage par lettre. Pour les mots en anglais minuscules, les deux conviennent ; pour le texte Unicode ou les tries clairsemés, une map permet d’économiser beaucoup de mémoire.

Où les tries sont-ils utilisés en pratique ?

La saisie semi-automatique et les suggestions de recherche parcourent un trie jusqu’au préfixe saisi et répertorient les mots qui en découlent. Les correcteurs orthographiques, les jeux de mots qui recherchent des mots du dictionnaire sur un plateau et les routeurs qui trouvent le préfixe d’adresse correspondant le plus long utilisent la même structure. Chaque fois que de nombreuses chaînes partagent le même début et que vous effectuez une recherche par début, un trie convient.

Python

def trieOps(ops, words):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Attendu

["null", "false", "true", "null", "true"]