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.