Easy to understand Python (Trie + DFS). Beats 95%


  • 0
    2
    class Solution(object):
        def findWords(self, board, words):
            """
            :type board: List[List[str]]
            :type words: List[str]
            :rtype: List[str]
            """
            trie = self.build_trie(words)
            result = set()
            for i in xrange(len(board)):
                for j in xrange(len(board[0])):
                    self.dfs(i, j, board, trie, result)
            return list(result)
            
        def build_trie(self, words):
            trie = {}
            for word in words:
                node = trie
                for ch in word:
                    if ch not in node:
                        node[ch] = {}
                    node = node[ch]
                node['#'] = word
            return trie
            
        
        def dfs(self, i, j, board, trie, result):
            if '#' in trie:
                result.add(trie['#'])
                
            if i < 0 or i >= len(board) or \
               j < 0 or j >= len(board[0]) or \
               board[i][j] not in trie:
                return
            
            ch = board[i][j] 
            board[i][j] = '0'
            trie = trie[ch]
    
            for di, dj in zip((-1, 1, 0, 0), (0, 0, 1, -1)):
                self.dfs(i+di, j+dj, board, trie, result)
            
            board[i][j] = ch    
    

Log in to reply
 

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