Implement Trie (Prefix Tree)

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

Un ensemble de hachage trouve des mots entiers en O(L) , mais ne peut pas répondre à une question sur un préfixe sans parcourir chaque mot. Stocker chaque préfixe dans un deuxième ensemble coûte 210 lettres pour un seul mot de 20 lettres. Un trie stocke chaque préfixe partagé une seule fois et répond aux deux questions en un seul parcours.

MoyenTrie

+10

Construisez un trie (arbre de préfixes) pour des mots en minuscules avec trois opérations : insert w ajoute le mot w, search w indique si w lui-même a été inséré, 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.

L’opération i est ops[i] appliquée à words[i]. Exécutez-les dans l’ordre sur un trie vide et renvoyez une chaîne pour chacune : "null" pour une insertion, "true" ou "false" pour une recherche ou une opération 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 pour 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] ne contient que 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: car commence par card, donc startsWith car vaut "true", mais car n’a jamais été inséré, donc la première recherche renvoie "false". Après insert car, 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, mais aucun n'est exactement te, donc startsWith vaut "true" et search vaut "false". Aucun mot ne commence par tex, et tea est un préfixe de lui-même.

Entrée: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Sortie: ["false", "false", "null", "true", "false", "true"]
Explication: Dans le trie vide, les deux requêtes renvoient "false". Après insert dog, la recherche le trouve, aucun mot ne commence par dogs, et do commence par dog.

Pour aller plus loin

Comment ajouteriez-vous une opération countPrefix p qui renvoie le nombre de mots distincts stockés commençant 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 à search, mais il n’a aucune notion de début, donc startsWith parcourrait tous les mots. Un arbre préfixe stocke chaque mot sous la forme d’un chemin de lettres depuis la racine : les mots qui commencent de la même façon partagent un chemin, et un indicateur marque la fin d’un mot stocké. Les deux requêtes se ramènent à un seul parcours d’au plus L liens.

Conservez une liste de mots et parcourez-la

Intuition

Conservez chaque mot inséré dans une liste. search w compare w à chaque mot stocké, et startsWith p vérifie si un mot stocké commence par p. C'est correct, car cela teste directement la définition. Avec n mots stockés, chaque requête nécessite jusqu'à n comparaisons portant sur jusqu'à L lettres : 1 000 mots et 1 000 requêtes représentent un million de comparaisons de chaînes.

Algorithme

Commencez avec une liste vide.
insert w : ajoutez w à la fin.
search w : renvoie si un mot stocké est égal à w.
startsWith p : renvoie si un mot stocké commence par p.

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 : des liens vers les enfants et un indicateur de fin

Intuition

Chaque nœud représente un préfixe, c’est-à-dire les lettres du chemin qui mène de la racine à ce nœud. Il contient un lien vers un enfant pour chaque lettre qui peut suivre (26 emplacements ou une map) et un indicateur isEnd qui indique si un mot stocké se termine exactement à cet endroit. L’insertion de tea crée les nœuds pour t, te et tea ; l’insertion de ten ajoute ensuite uniquement ten, car les deux mots partagent le chemin pour te.

Un parcours qui rencontre un lien manquant prouve qu’aucun mot stocké ne commence par ces lettres : tex s’arrête à te, qui n’a pas de lien x. Un parcours qui atteint la fin se trouve sur le nœud correspondant à la requête : startsWith renvoie donc true et search répond en fonction de l’indicateur. Le nœud pour te existe, mais son indicateur est désactivé ; search te renvoie donc false. Chaque opération suit au plus L liens, quel que soit le nombre de mots stockés, et le trie contient un nœud par préfixe distinct.

Algorithme

Créez une racine sans lien enfant et avec isEnd désactivé.
insert w : depuis la racine, suivez le lien correspondant à chaque lettre, en créant le nœud s’il est manquant. Activez isEnd sur le dernier nœud.
find(p) : depuis la racine, suivez le lien correspondant à chaque lettre ; ne renvoyez rien dès qu’un lien est manquant, sinon renvoyez le nœud atteint.
search w : vrai lorsque find(w) renvoie un nœud dont isEnd est activé.
startsWith p : vrai lorsque find(p) renvoie un nœud.

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

Faire répondre search true dès que le chemin existe. Après insert card, le chemin de car existe, mais search car doit répondre false.
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 besoin de son indicateur.
Créer un nouvel enfant lorsque le lien existe déjà. Insérer ten avec un nouveau nœud t fait perdre tea.
Lire au-delà de la fin du chemin. startsWith sunny alors que seul sun est stocké doit s’arrêter au premier lien manquant et répondre false.

Questions fréquentes3

Quelle est la complexité temporelle d’un trie ?

Insert, search et startsWith suivent chacun un lien par lettre, donc chacun prend O(L) pour un mot de longueur L, quel que soit le nombre de mots stockés. L’espace est de O(T) nœuds pour T lettres insérées au total, chaque nœud contenant jusqu’à 26 liens enfants.

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

Un ensemble de hachage trouve des mots entiers en O(L), mais ne peut pas répondre à une question sur un préfixe sans parcourir chaque mot. Stocker chaque préfixe dans un deuxième ensemble coûte 210 lettres pour un seul mot de 20 lettres. Un trie stocke chaque préfixe partagé une seule fois et répond aux deux questions en un seul parcours.

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

Un tableau trouve un enfant avec un seul index, mais coûte 26 emplacements par nœud, même pour un nœud avec un seul enfant. Une map ne stocke que les enfants existants et fonctionne avec n’importe quel alphabet, au prix d’un hachage par lettre. Pour l’anglais en minuscules, les deux conviennent ; pour Unicode ou les tries clairsemés, une map économise de la mémoire.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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