Word Search II 330ms Python DFS+simple trie


  • 0
    S

    Share a python solution. borrow the idea of building a simpler trie. it took 332ms. there are some solutions below 300ms. not sure how to further improve.

    class Solution(object):
        def findWords(self, board, words):
            """
            :type board: List[List[str]]
            :type words: List[str]
            :rtype: List[str]
            """
            def search(i,j, helper, res, temp):
                if  i<0 or j<0 or i>=row or j>=col or helper=={} or board[i][j] not in helper:
                    return 
                else:
                    letter=board[i][j];helper=helper[letter]
                    if '#' in helper:
                        res.append(temp+letter)
                        helper.pop('#')
                
                    holder, board[i][j]=board[i][j], '.'
                    search(i+1, j, helper, res, temp+letter) 
                    search(i-1, j, helper, res, temp+letter) 
                    search(i, j+1, helper, res, temp+letter)
                    search(i, j-1, helper, res, temp+letter)
                    board[i][j]=holder
                           
            
            trie={}
            for word in words:
                t=trie
                for letter in word:
                    if letter not in t:
                        t[letter]={}
                    t=t[letter]
                t['#']='#'
                    
            res=[]; col=len(board[0]); row=len(board)
            for i in xrange(row):
                for j in xrange(col):
                    search(i, j, trie, res,'')
            return res

Log in to reply
 

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