structures - github python examples

Trie tree match performance en búsqueda de palabras

Question

He depurado algunas soluciones similares, pero me pregunto si podríamos mejorar Trie Tree a un prefijo de coincidencia parcial (en el método de búsqueda de la clase Trie, el método de búsqueda actual solo verifica si una palabra completa coincide o no) para mejorar el rendimiento, lo que podría volver de un camino equivocado antes? No tengo mucha confianza en la idea, así que busque consejo antes.

Publico una de las soluciones similares. Gracias.

Dado un tablero 2D y una lista de palabras del diccionario, encuentra todas las palabras en el tablero.

Cada palabra debe construirse a partir de letras de celdas secuencialmente adyacentes, donde las celdas "adyacentes" son las vecinas horizontal o verticalmente. La misma celda de letra no puede usarse más de una vez en una palabra.

Por ejemplo, Dadas palabras = ["oath","pea","eat","rain"] y tabla =

[
[''o'',''a'',''a'',''n''],
[''e'',''t'',''a'',''e''],
[''i'',''h'',''k'',''r''],
[''i'',''f'',''l'',''v'']
]

Regresar ["comer", "juramento"]

class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie():
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True
def search(self, word):
node = self.root
for w in word:
node = node.children.get(w)
if not node:
return False
return node.isWord
class Solution(object):
def findWords(self, board, words):
res = []
trie = Trie()
node = trie.root
for w in words:
trie.insert(w)
for i in xrange(len(board)):
for j in xrange(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
if node.isWord:
res.append(path)
node.isWord = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
return
tmp = board[i][j]
node = node.children.get(tmp)
if not node:
return
board[i][j] = "#"
self.dfs(board, node, i+1, j, path+tmp, res)
self.dfs(board, node, i-1, j, path+tmp, res)
self.dfs(board, node, i, j-1, path+tmp, res)
self.dfs(board, node, i, j+1, path+tmp, res)
board[i][j] = tmp

Answer 1

No veo nada malo de la parte Trie en tu código.

Pero creo que el diseño original del trie ya ha regresado pronto al detectar cualquier desajuste.

En realidad, usualmente solo uso dict regular como trie en lugar de defaultDict + TrieNode para evitar que el problema se complique demasiado. Solo necesita configurar una tecla "#" si un determinado nodo es una palabra válida. Y, durante la inserción, simplemente haga el node[w] = {} .

Si hace esto, su código puede simplificarse significativamente y la devolución temprana será sencilla, ya que no tendrá una clave "incorrecta" en un nodo.

Por ejemplo, un trie simple que contenga solo ''ab'' se verá así: {''a'': {''b'': {''#'': {}}} . Por lo tanto, cuando busque ''cd'' , tan pronto como se dé cuenta de que no hay una clave ''c'' en el dictado más externo, puede devolver false. Esta implementación es similar a la suya, pero creo que es más fácil de entender.