Búsqueda con comodines y expresiones regulares en un trie

La búsqueda estándar en un trie gestiona caracteres exactos. La búsqueda con comodines añade un carácter especial '.' que coincide con cualquier carácter individual. Al encontrar un '.' durante la búsqueda, en lugar de seguir un único hijo específico, debemos probar todos los hijos: se produce una ramificación. Esta es la idea central de LeetCode 211, «Design Add and Search Words Data Structure». Cada '.' multiplica las rutas de búsqueda por el número de hijos de ese nivel.

Implemente la búsqueda con comodines mediante una función auxiliar recursiva de DFS. Para cada carácter del patrón: si es un carácter literal, siga el hijo específico (o devuelva False si falta); si es '.', haga una llamada recursiva para todos los hijos y devuelva True si alguna tiene éxito. Al final del patrón, devuelva node.is_end.

Cuando se encuentra un '.', llamamos a any(dfs(child, i+1) for child in node.children.values()). El generador any() utiliza evaluación de cortocircuito: se detiene en cuanto un hijo devuelve True. Esto evita exploraciones innecesarias. En el peor caso (un patrón compuesto únicamente por '.'), exploramos todas las rutas; la complejidad es O(26^k), donde k es el número de puntos, por lo que patrones como '....' resultan costosos en tries grandes.

Un enfoque iterativo utiliza una cola de pares (node, index). Comience con (root, 0). Para cada par, si index == len(word) y node.is_end, devuelva True. De lo contrario, procese el carácter actual: para '.', añada todos los hijos a la cola; para un carácter literal, añada únicamente el hijo coincidente. En esencia, se trata de un BFS sobre las rutas del trie.

Para un patrón sin comodines, la búsqueda es O(m). Para un patrón con k comodines, el peor caso es O(26^k × m): es exponencial respecto al número de comodines. En la práctica, los comodines suelen ser poco frecuentes y el trie no suele ser profundo, por lo que el rendimiento es aceptable. En patrones compuestos completamente por comodines (por ejemplo, para encontrar todas las palabras de longitud k), la búsqueda degenera en un recorrido completo del trie.

Ampliar la búsqueda a expresiones regulares completas (por ejemplo, '*', que coincide con cero o más caracteres) requiere un tratamiento diferente. Un '*' puede coincidir con cualquier sufijo, por lo que, al encontrarlo, debemos probar todas las rutas del trie desde el nodo actual. La coincidencia de expresiones regulares reales en un trie es compleja y normalmente se reserva para construcciones NFA/DFA. En entrevistas, el patrón estándar son los comodines de un solo carácter ('.').

La coincidencia de patrones glob con '?' (cualquier carácter individual) y '*' (cualquier secuencia, incluida la vacía) se puede implementar mediante DP. Si se implementa en un trie, '?' corresponde a una ramificación de un solo nivel (como '.') y '*' corresponde a un DFS de varios niveles. El enfoque combinado de DP es el siguiente: dp[i][j] = True si pattern[0..i] coincide con string[0..j]. Por lo general, el entrevistador especifica qué variante se debe implementar.

Los tries con comodines se utilizan en las tablas de enrutamiento IP, donde '*' actúa como comodín de prefijo. Un router almacena prefijos de ruta como '192.168.*' y compara las direcciones entrantes. La coincidencia del prefijo más largo (gana la ruta más específica) se implementa recorriendo el trie hasta la mayor profundidad posible y utilizando la última coincidencia encontrada. Esta es una aplicación real de las operaciones de prefijo y comodines de los tries.

Cuando un nodo del trie no tiene hijos (es una hoja) y is_end = False, cualquier búsqueda que llegue a él devuelve False. Durante la búsqueda con comodines, omitir estos nodos sin salida antes de realizar la recursión permite evitar llamadas innecesarias. Mantener un word_count en cada nodo (el total de palabras del subárbol) permite omitir un subárbol completo si ninguna palabra puede coincidir con las restricciones de longitud restantes del patrón.

Una clase WordDictionary limpia y lista para entrevistas que combina la inserción y la búsqueda con comodines de punto en una sola clase. Esta es la implementación exacta que se espera para LeetCode 211. La búsqueda recursiva con any() de cortocircuito es concisa y demuestra claramente la lógica de ramificación a los entrevistadores.

dict.setdefault(key, default) devuelve el valor de key si está presente; de lo contrario, inserta default y lo devuelve. Usar node.setdefault(c, {}) en la inserción elimina la comprobación if-else: crea el diccionario hijo si falta y lo devuelve en cualquier caso. Esto convierte la inserción en un recorrido de una sola línea: for c in word: node = node.setdefault(c, {}). Limpio y propio del estilo de Python.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió: el comodín '.' requiere ramificarse hacia todos los hijos en la posición correspondiente mediante un DFS recursivo, usar any() con un generador proporciona evaluación de cortocircuito para terminar antes, y setdefault permite realizar una inserción compacta del trie en una sola línea. A continuación combinaremos tries y backtracking para resolver Word Search II: encontrar varias palabras simultáneamente en un tablero 2D.