Design Add and Search Words Data Structure

Q: ¿Cuál es la complejidad temporal de agregar y buscar palabras?

Añadir una palabra de longitud L toma O(L) , y una búsqueda sin puntos también, sin importar cuántas palabras estén almacenadas. Una búsqueda con d puntos toma O(26^d · L) en el peor caso. La memoria es de O(T) nodos para T letras añadidas.

MedioTrie Backtracking

+10

Construye un diccionario de palabras con dos operaciones. addWord w almacena la palabra w. search p indica si alguna palabra almacenada coincide con el patrón p: tiene la misma longitud y, en cada posición, el patrón contiene la misma letra o un punto ., que representa cualquier letra.

La operación i es ops[i] sobre la palabra o el patrón words[i]. Ejecútalas en orden sobre un diccionario vacío y devuelve una cadena por cada una: "null" para un addWord, "true" o "false" para un search.

Función

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

opsstring-array: las operaciones, en el orden en que se ejecutan
wordsstring-array: la palabra que se va a añadir o el patrón que se va a buscar, uno por operación
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ ops.length ≤ 2500
words.length == ops.length
Each ops[i] es addWord o search.
1 ≤ words[i].length ≤ 20
Una palabra que se va a añadir contiene únicamente letras minúsculas del inglés.
Un patrón de búsqueda contiene letras minúsculas del inglés y como máximo 3 puntos.

Ejemplos

Entrada: ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Salida: ["null", "null", "true", "false", "false", "true"]
Explicación: r.se coincide con ambas palabras: el punto abarca la o de rose y la i de rise. Un punto nunca representa una letra que falta, así que ros y rose. no coinciden. ..s. coincide, ya que ambas palabras tienen una s en tercer lugar.

Entrada: ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
Salida: ["false", "null", "true", "true", "false"]
Explicación: El diccionario empieza vacío, así que ... no encuentra nada. Una vez que se agrega sky, tanto ... como s.y coinciden con él, mientras que sk es demasiado corto.

Entrada: ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
Salida: ["null", "null", "true", "false", "true"]
Explicación: El primer punto de ma..o puede ser la p de maple o la n de mango; maple termina en e, pero mango encaja. Ninguna palabra termina en y, así que m...y no coincide, y m.p.e coincide con maple.

Para ir más allá

¿Cómo ampliarías search si un patrón también pudiera contener *, que representa cualquier secuencia de letras, incluso una vacía?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un punto significa que la búsqueda no puede especificar la letra que quiere: ma..o representa 676 palabras posibles, y solo importan las que están almacenadas. En un trie, las palabras que empiezan igual comparten un camino. Una letra del patrón sigue un enlace, un punto se ramifica solo hacia los hijos que existen y una búsqueda en profundidad retrocede desde las ramas muertas.

Compara el patrón con cada palabra almacenada

Intuición

Guarda las palabras añadidas en una lista y compara cada una con el patrón: misma longitud y, en cada posición, un punto o la misma letra. Esa es la definición de una coincidencia, comprobada con cada palabra almacenada, así que la respuesta es correcta.

Cada búsqueda recorre toda la lista, O(n·L) para n palabras de hasta L letras, incluso si el patrón no contiene ningún punto. 1,250 añadidos seguidos de 1,250 búsquedas comprueban 1,250 × 1,250 = 1,562,500 palabras.

Algoritmo

Mantén las palabras añadidas en una lista. Para addWord w, añade w y registra "null".
Para search p, compara p con cada palabra de la misma longitud, posición por posición, permitiendo que un punto acepte cualquier letra.
Registra "true" en la primera coincidencia, o "false" si no hay ninguna.

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 result

Trie con una búsqueda en profundidad en puntos

Intuición

Coloca las palabras en un trie: rose y rise comparten el nodo r y después se separan en o e i. Una marca de final señala cada nodo donde termina una palabra almacenada. Un patrón de letras es un recorrido por el trie. Un punto puede ser cualquier letra, así que en un punto prueba cada hijo existente y devuelve true en cuanto uno lleve a una coincidencia.

Para ma..o, el nodo de ma tiene los hijos p y n. A través de p, el segundo punto llega a l, que no tiene ningún hijo o, así que la búsqueda retrocede y prueba n: g y después o, donde termina mango.

Una coincidencia debe consumir todo el patrón en un nodo marcado, lo que aclara la longitud: ros se detiene en un nodo sin marcar, y rose. se queda sin enlaces. Un punto abre como máximo 26 ramas, así que d puntos visitan como máximo 26^d · L nodos, y un patrón sin puntos cuesta O(L).

Algoritmo

Cada nodo tiene enlaces a sus hijos y una bandera de fin, desactivada al principio.
Para addWord w: recorre w desde la raíz, creando los nodos que falten, y activa la bandera de fin donde se detenga el recorrido.
match(node, i): si i es la longitud del patrón, devuelve la bandera de fin del nodo.
Si p[i] es una letra, devuelve false si falta su hijo; de lo contrario, devuelve match(child, i+1). Si es un punto, devuelve true si match(child, i+1) tiene éxito para algún hijo existente; de lo contrario, devuelve false.
Registra match(root, 0) por búsqueda y "null" por cada adición.

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

Errores comunes y casos límite

Dejar que el primer hijo decida el punto. En ma..o, la rama p falla y la rama n tiene éxito, así que el código que devuelve el resultado del primer hijo responde false cuando prueba primero con p. Responde false solo después de que fallen todos los hijos.
Responder true cuando el patrón se acaba en cualquier nodo. Después de agregar rose, ros llega a un nodo, pero ninguna palabra termina ahí. Comprueba la marca de fin.
Permitir que un punto coincida con una letra inexistente. card. coincide con cards, pero no con card.
Tratar un punto como una letra. Indexar un arreglo de 26 posiciones con '.' - 'a' accede a una posición fuera del arreglo, así que comprueba primero si es un punto.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de agregar y buscar palabras?

Añadir una palabra de longitud L toma O(L), y una búsqueda sin puntos también, sin importar cuántas palabras estén almacenadas. Una búsqueda con d puntos toma O(26^d · L) en el peor caso. La memoria es de O(T) nodos para T letras añadidas.

¿Puedes resolverlo con un conjunto hash en lugar de un trie?

Sí, con ciertas concesiones. Un conjunto resuelve un patrón sin puntos con una sola búsqueda. Para los puntos, tienes que recorrer cada palabra almacenada de esa longitud, O(n·L), o sustituir cada punto por las 26 letras y buscar cada resultado: 17,576 búsquedas para tres puntos.

¿La búsqueda en el trie debería ser recursiva o iterativa?

Ambas opciones funcionan. La recursión avanza un nivel por cada letra del patrón, como máximo 20 en este caso, así que la pila de llamadas se mantiene pequeña. Una versión iterativa mantiene una pila de pares (node, position) y apila cada hijo en un punto.

def wordDictionaryOps(ops, words):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

ops = ["addWord", "addWord", "search", "search", "search", "search"]
words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]

Salida Esperada

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