Design Add and Search Words Data Structure
Crea un dizionario di parole con due operazioni. addWord w memorizza la parola w. search p indica se una parola memorizzata corrisponde al modello p: stessa lunghezza e, in ogni posizione, il modello contiene la stessa lettera oppure un punto ., che rappresenta una qualsiasi lettera.
L’operazione i è ops[i] sulla parola o sul modello words[i]. Esegui le operazioni nell’ordine indicato su un dizionario vuoto e restituisci una stringa per ciascuna: "null" per un addWord, "true" o "false" per un search.
Funzione
- opsstring-array
- le operazioni, nell'ordine in cui vengono eseguite
- wordsstring-array
- la parola da aggiungere o il modello da cercare, uno per operazione
- Restituiscestring-array
- una risposta per operazione, come testo
Vincoli
1 ≤ ops.length ≤ 2500words.length == ops.length- Ogni
ops[i]èaddWordoppuresearch. 1 ≤ words[i].length ≤ 20- Una parola da aggiungere contiene solo lettere inglesi minuscole.
- Un modello da cercare contiene lettere inglesi minuscole e al massimo 3 punti.
Esempi
- Input
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- Output
- ["null", "null", "true", "false", "false", "true"]
- Spiegazione
r.secorrisponde a entrambe le parole: il punto copre la o dirosee la i dirise. Un punto non rappresenta mai una lettera mancante, quindiroserose.non corrispondono...s.corrisponde, poiché entrambe le parole hanno la s come terza lettera.
- Input
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- Output
- ["false", "null", "true", "true", "false"]
- Spiegazione
- Il dizionario inizia vuoto, quindi
...non trova nulla. Una volta aggiuntasky, sia...sias.ycorrispondono, mentreskè troppo corta.
- Input
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- Output
- ["null", "null", "true", "false", "true"]
- Spiegazione
- Il primo punto di
ma..opuò essere la p dimapleo la n dimango;maplefinisce con e, mamangocorrisponde. Nessuna parola finisce con y, quindim...ynon corrisponde, mentrem.p.ecorrisponde amaple.
Per approfondire
Come estenderesti search se un pattern potesse contenere anche *, che rappresenta una sequenza qualsiasi di lettere, anche vuota?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Senza punti, un insieme hash delle parole memorizzate risponderebbe a ogni ricerca con un solo accesso. Un punto cambia le cose:
c.tpotrebbe esserecat,cotoppurecut. Quale struttura ti permette di seguire una parola una lettera alla volta e vedere tutte le lettere che possono venire dopo?Memorizza le parole in un trie, con un flag su ogni nodo in cui termina una parola memorizzata. Una lettera nel pattern segue un collegamento figlio. Un punto può rappresentare qualsiasi lettera, quindi deve provare ogni figlio del nodo corrente e tornare indietro quando un ramo finisce in un vicolo cieco.
Scrivi una funzione ricorsiva
match(node, i). Alla fine del modello, rispondi con il flag di fine del nodo. In corrispondenza di una lettera, segui il nodo figlio oppure fallisci se manca. In corrispondenza di un punto, restituisci true non appenamatch(child, i+1)ha esito positivo per un nodo figlio qualsiasi, e false se non succede per nessuno.
Soluzione
Un punto indica che una ricerca non può specificare la parola desiderata: ma..o rappresenta 676 parole possibili, e contano solo quelle memorizzate. In un trie, le parole che iniziano allo stesso modo condividono un percorso. Una lettera nel modello segue un collegamento, un punto si dirama solo verso i figli esistenti e una ricerca in profondità torna indietro dai rami senza sbocchi.
Confronta il modello con ogni parola memorizzata
Intuizione
Conserva le parole aggiunte in una lista e confronta ciascuna con il modello: stessa lunghezza e, in ogni posizione, un punto oppure la stessa lettera. Questa è la definizione di corrispondenza, verificata rispetto a ogni parola memorizzata, quindi la risposta è corretta.
Ogni ricerca esamina l’intera lista, O(n·L) per n parole di al massimo L lettere, anche quando il modello non contiene punti. 1,250 aggiunte seguite da 1,250 ricerche comportano il controllo di 1,250 × 1,250 = 1,562,500 parole.
Algoritmo
- Mantieni le parole aggiunte in una lista. Per
addWord w, aggiungiwe registra"null". - Per
search p, confrontapcon ogni parola della stessa lunghezza, posizione per posizione, consentendo a un punto di accettare qualsiasi lettera. - Registra
"true"al primo riscontro, oppure"false"se non ce ne sono.
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 resultTrie con una ricerca in profondità sui punti
Intuizione
Inserisci le parole in un trie: rose e rise condividono il nodo r, poi si dividono in o e i. Un contrassegno di fine indica ogni nodo in cui termina una parola memorizzata. Una sequenza di lettere corrisponde a un percorso lungo il trie. Un punto può rappresentare qualsiasi lettera, quindi in corrispondenza di un punto prova ogni figlio esistente e restituisci true non appena uno porta a una corrispondenza.
Per ma..o, il nodo di ma ha come figli p e n. Passando per p, il secondo punto raggiunge l, che non ha un figlio o, quindi la ricerca torna indietro e prova n: g, poi o, che completa mango.
Una corrispondenza deve consumare l’intero schema su un nodo contrassegnato, il che chiarisce la questione della lunghezza: ros si ferma su un nodo non contrassegnato, mentre rose. esaurisce i collegamenti. Un punto apre al massimo 26 rami, quindi d punti visitano al massimo 26^d · L nodi e uno schema senza punti ha un costo di O(L).
Algoritmo
- Ogni nodo ha collegamenti ai figli e un flag di fine, disattivato all'inizio.
- Per
addWord w: percorriwdalla radice, creando i nodi mancanti, e imposta il flag di fine nel punto in cui il percorso si interrompe. match(node, i): seiè la lunghezza del pattern, restituisci il flag di fine del nodo.- Se
p[i]è una lettera, restituisci false se manca il figlio corrispondente, altrimentimatch(child, i+1). Se è un punto, restituisci true sematch(child, i+1)ha esito positivo per uno qualsiasi dei figli esistenti, altrimenti false. - Registra
match(root, 0)per ogni ricerca,"null"per ogni aggiunta.
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
Trappole e casi limite
- Lasciare che il primo figlio determini il risultato del punto. In
ma..oil ramo p fallisce e il ramo n ha successo, quindi il codice che restituisce il risultato del primo figlio risponde false quando prova prima p. Rispondi false solo dopo che tutti i figli hanno fallito. - Rispondere true quando il pattern termina in un qualsiasi nodo. Dopo aver aggiunto
rose,rosraggiunge un nodo, ma lì non termina nessuna parola. Controlla il flag di fine. - Lasciare che un punto corrisponda a una lettera mancante.
card.corrisponde acardsma non acard. - Considerare un punto come una lettera. Accedere a un array di 26 posizioni con
'.' - 'a'legge fuori dall'array, quindi verifica prima se si tratta del punto.
Domande frequenti3
Qual è la complessità temporale di Add e Search Words?
Aggiungere una parola di lunghezza L richiede O(L), così come una ricerca senza punti, indipendentemente dal numero di parole memorizzate. Una ricerca con d punti richiede O(26^d · L) nel caso peggiore. La memoria è di O(T) nodi per T lettere aggiunte.
Riesci a risolverlo con un insieme hash invece che con un trie?
Sì, con dei compromessi. Un set corrisponde a un modello senza punti con una sola ricerca. Per i punti, devi scansionare tutte le parole memorizzate di quella lunghezza, O(n·L), oppure sostituire ogni punto con tutte le 26 lettere e cercare ogni risultato: 17,576 ricerche per tre punti.
La ricerca nel trie dovrebbe essere ricorsiva o iterativa?
Entrambe le soluzioni funzionano. La ricorsione procede di un livello per ogni lettera del pattern, al massimo 20 in questo caso, quindi lo stack delle chiamate rimane piccolo. Una versione iterativa mantiene uno stack di coppie (nodo, posizione) e inserisce ogni figlio in corrispondenza di un punto.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def wordDictionaryOps(ops, words):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Output atteso
["null", "null", "true", "false", "false", "true"]