Python dfs solution (directly use Trie implemented).


  • 15
    C

    Here is an implementation based on Implement Trie in LeetCode. TrieNode, Trie, Solution are treated as seperated classes.

    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
    

  • 0
    W

    @caikehe Great solution, but no need to implement Trie.search() since the search is essentially done by dfs.


  • 0
    C

    @caikehe said in Python dfs solution (directly use Trie implemented).:

    collections.defaultdict(TrieNode)

    What does this code actually do?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.