Python DFS + Backtracking with Explanation


  • 0
    B

    The idea is to simply run dfs from all possible cell and keep checking if the current string is in the prefix set.

    class Solution(object):
        def findWords(self, board, words):
    
            n = len(board)
            if n==0: return []
            m = len(board[0])
            
            dirs = [[-1, 0], [0, -1], [0, 1], [1, 0]]
            ans = set()
            words_set = set(words)
            prefix_set = set()
    
            for word in words:
                for i in range(len(word)-1):
                    prefix_set.add(word[:i+1])
            visited = [[False]*m for i in range(n)]
            
            def dfs(visit, cur_w, x, y):
                if cur_w in words_set:
                    ans.add(cur_w)
                if cur_w not in prefix_set:
                    return
                visit[x][y] = True
                for idx, idy in dirs:
                    new_x, new_y = x+idx, y+idy
                    if new_x>=0 and new_x<n and new_y>=0 and new_y<m and not visit[new_x][new_y]:
                        dfs(visit, cur_w+board[new_x][new_y], new_x, new_y)
                visit[x][y] = False
            
            for i in range(n):
                for j in range(m):
                    dfs(visited, board[i][j], i, j)
                    
            return list(ans)
    

Log in to reply
 

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