Design Add and Search Words Data Structure
Créez un dictionnaire de mots avec deux opérations. addWord w stocke le mot w. search p indique si un mot stocké correspond au motif p : il a la même longueur et, à chaque position, le motif contient la même lettre ou un point ., qui représente n’importe quelle lettre.
L’opération i est ops[i] sur le mot ou le motif words[i]. Exécutez-les dans l’ordre sur un dictionnaire vide et renvoyez une chaîne pour chacune : "null" pour un addWord, "true" ou "false" pour un search.
Fonction
- opsstring-array
- les opérations, dans l’ordre où elles s’exécutent
- wordsstring-array
- le mot à ajouter ou le motif à rechercher, un par opération
- Renvoiestring-array
- une réponse par opération, sous forme de texte
Contraintes
1 ≤ ops.length ≤ 2500words.length == ops.length- Chaque
ops[i]estaddWordousearch. 1 ≤ words[i].length ≤ 20- Le mot à ajouter ne contient que des lettres minuscules anglaises.
- Un motif de recherche comporte des lettres minuscules anglaises et au plus 3 points.
Exemples
- Entrée
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- Sortie
- ["null", "null", "true", "false", "false", "true"]
- Explication
r.secorrespond aux deux mots : le point remplace le o deroseet le i derise. Un point ne représente jamais une lettre manquante, doncrosetrose.ne correspondent pas...s.correspond, car les deux mots ont un s en troisième position.
- Entrée
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- Sortie
- ["false", "null", "true", "true", "false"]
- Explication
- Le dictionnaire est vide au départ, donc
...ne trouve rien. Une fois queskyest ajouté,...ets.ycorrespondent tous deux à ce mot, tandis queskest trop court.
- Entrée
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- Sortie
- ["null", "null", "true", "false", "true"]
- Explication
- Le premier point de
ma..opeut être le p demapleou le n demango;maplese termine par e, maismangoconvient. Aucun mot ne se termine par y, doncm...yne correspond à rien, etm.p.ecorrespond àmaple.
Pour aller plus loin
Comment étendriez-vous search si un motif pouvait aussi contenir *, qui représente toute séquence de lettres, même vide ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Sans points, un ensemble de hachage des mots stockés répondrait à chaque recherche en une seule consultation. Un point change la donne :
c.tpourrait êtrecat,cotoucut. Quelle structure te permet de parcourir un mot une lettre à la fois et de voir toutes les lettres qui peuvent suivre ?Stockez les mots dans un trie, avec un indicateur sur chaque nœud où se termine un mot stocké. Une lettre du motif suit un lien vers un enfant. Un point peut représenter n’importe quelle lettre : il faut donc essayer chaque enfant du nœud actuel et revenir en arrière lorsqu’une branche aboutit à une impasse.
Écrivez une fonction récursive
match(node, i). À la fin du motif, répondez avec l’indicateur de fin du nœud. Pour une lettre, suivez cet enfant, ou échouez s’il est absent. Pour un point, renvoyez true dès quematch(child, i+1)réussit pour un enfant, et false si aucun ne réussit.
Solution
Un point signifie qu’une recherche ne peut pas nommer le mot qu’elle cherche : ma..o représente 676 mots possibles, et seuls ceux qui sont stockés comptent. Dans un trie, les mots qui commencent de la même façon partagent un chemin. Une lettre du motif suit un lien, un point explore uniquement les enfants qui existent, et une recherche en profondeur revient en arrière lorsqu’elle atteint des branches sans issue.
Comparez le motif avec chaque mot stocké
Intuition
Conserve les mots ajoutés dans une liste et teste chacun d’eux par rapport au motif : même longueur, et à chaque position, un point ou la même lettre. C’est la définition d’une correspondance, vérifiée par rapport à chaque mot enregistré, donc la réponse est correcte.
Chaque recherche parcourt toute la liste, O(n·L) pour n mots de jusqu’à L lettres, même pour un motif sans point. 1,250 ajouts suivis de 1,250 recherches testent 1,250 × 1,250 = 1,562,500 mots.
Algorithme
- Gardez les mots ajoutés dans une liste. Pour
addWord w, ajoutezwet enregistrez"null". - Pour
search p, comparezpà chaque mot de même longueur, position par position, en laissant un point accepter n'importe quelle lettre. - Enregistrez
"true"à la première correspondance, ou"false"s'il n'y en a aucune.
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return resultArbre préfixe avec une recherche en profondeur sur les points
Intuition
Insère les mots dans un trie : rose et rise partagent le nœud r, puis se séparent en o et i. Un indicateur de fin marque chaque nœud où se termine un mot stocké. Une suite de lettres correspond à un parcours dans le trie. Un point peut représenter n’importe quelle lettre : à un point, essaie donc chaque enfant existant et renvoie true dès que l’un d’eux mène à une correspondance.
Pour ma..o, le nœud de ma a pour enfants p et n. En passant par p, le deuxième point mène à l, qui n’a pas d’enfant o ; la recherche revient donc en arrière et essaie n : g, puis o, qui termine mango.
Une correspondance doit consommer tout le motif et aboutir sur un nœud marqué, ce qui règle la question de la longueur : ros s’arrête sur un nœud non marqué, et rose. arrive au bout des liens. Un point ouvre au plus 26 branches ; ainsi, d points visitent au plus 26^d · L nœuds, et un motif sans point coûte O(L).
Algorithme
- Chaque nœud possède des liens vers ses enfants et un indicateur de fin, désactivé au départ.
- Pour
addWord w: parcourezwdepuis la racine, en créant les nœuds manquants, puis activez l’indicateur de fin à l’endroit où le parcours s’arrête. match(node, i): siiest égal à la longueur du motif, renvoyez l’indicateur de fin du nœud.- Si
p[i]est une lettre, renvoyez false si son enfant est manquant, sinonmatch(child, i+1). S’il s’agit d’un point, renvoyez true simatch(child, i+1)réussit pour un enfant existant quelconque, sinon false. - Enregistrez
match(root, 0)pour chaque recherche,"null"pour chaque ajout.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(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 search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
Pièges et cas limites
- Laisser le premier enfant décider du résultat d’un point. Dans
ma..o, la branche p échoue et la branche n réussit, donc le code qui renvoie le résultat du premier enfant répond false lorsqu’il essaie p en premier. Répondre false seulement après l’échec de tous les enfants. - Répondre true lorsque le motif arrive à sa fin sur n’importe quel nœud. Après avoir ajouté
rose,rosatteint un nœud, mais aucun mot ne se termine à cet endroit. Vérifier le indicateur de fin. - Laisser un point correspondre à une lettre manquante.
card.correspond àcards, mais pas àcard. - Traiter un point comme une lettre. L’indexation d’un tableau de 26 cases avec
'.' - 'a'lit en dehors du tableau ; il faut donc tester le point en premier.
Questions fréquentes3
Quelle est la complexité temporelle de Add et Search Words ?
L'ajout d'un mot de longueur L prend O(L), tout comme une recherche sans point, quel que soit le nombre de mots stockés. Une recherche avec d points prend O(26^d · L) dans le pire des cas. La mémoire utilisée est de O(T) nœuds pour T lettres ajoutées.
Peux-tu le résoudre avec un ensemble de hachage au lieu d’un trie ?
Oui, avec des compromis. Un ensemble répond à un motif sans points en une seule recherche. Pour les points, vous devez soit parcourir chaque mot stocké de cette longueur, O(n·L), soit remplacer chaque point par chacune des 26 lettres et rechercher chaque résultat, soit 17 576 recherches pour trois points.
La recherche dans le trie doit-elle être récursive ou itérative ?
Les deux fonctionnent. La récursion avance d’un niveau par lettre du motif, au maximum 20 ici, donc la pile d’appels reste petite. Une version itérative conserve une pile de paires (node, position) et y empile chaque enfant lorsqu’elle rencontre un point.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def wordDictionaryOps(ops, words):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Résultat attendu
["null", "null", "true", "false", "false", "true"]