Python code use trie and dfs 380ms


  • 24
    Y
    class Solution:
        # @param {character[][]} board
        # @param {string[]} words
        # @return {string[]}
        def findWords(self, board, words):
        #make trie
            trie={}
            for w in words:
                t=trie
                for c in w:
                    if c not in t:
                        t[c]={}
                    t=t[c]
                t['#']='#'
            self.res=set()
            self.used=[[False]*len(board[0]) for _ in range(len(board))]
            for i in range(len(board)):
                for j in range(len(board[0])):
                    self.find(board,i,j,trie,'')
            return list(self.res)
        
        def find(self,board,i,j,trie,pre):
            if '#' in trie:
                self.res.add(pre)
            if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
                return
            if not self.used[i][j] and board[i][j] in trie:
                self.used[i][j]=True
                self.find(board,i+1,j,trie[board[i][j]],pre+board[i][j])
                self.find(board,i,j+1,trie[board[i][j]],pre+board[i][j])
                self.find(board,i-1,j,trie[board[i][j]],pre+board[i][j])
                self.find(board,i,j-1,trie[board[i][j]],pre+board[i][j])
                self.used[i][j]=False

  • 12
    C

    Really nice way to build trie(). For space saving purpose, I rewrite your code in which way we don't need the "self.used" global variable:

    def findWords(self, board, words):
        trie = {}
        for w in words:
            t = trie
            for c in w:
                if c not in t:
                    t[c] = {}
                t = t[c]
            t['#'] = '#'
        res = []
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.find(board, i, j, trie, '', res)
        return list(set(res))
    
    def find(self, board, i, j, trie, path, res):
        if '#' in trie:
            res.append(path)
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j] not in trie:
            return
        tmp = board[i][j]
        board[i][j] ="@"
        self.find(board, i+1, j, trie[tmp], path+tmp, res)
        self.find(board, i, j+1, trie[tmp], path+tmp, res)
        self.find(board, i-1, j, trie[tmp], path+tmp, res)
        self.find(board, i, j-1, trie[tmp], path+tmp, res)
        board[i][j] = tmp

  • -1
    H

    board[i] is a string ,'board[i][j] ="@" 'is not be supported.


  • 0
    S

    indeed, the way of building trie saves a lot of time.


Log in to reply
 

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