Word Search II (Deprecated)

Given a 2-D array of characters and a list of valid words, find the number of words on the board. Tags: Recursion, Search, Trees

Try It!

Discussion

Video

Solution

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        visited = [[False for c in range(len(board[0]))] for r in range(len(board))]
        ans = set()
        
        trie = {}
        for word in words:
            level = trie
            for letter in word:
                if letter not in level:
                    level[letter] = {}
                level = level[letter]
            level['#'] = '#'
            
        for r in range(len(board)):
            for c in range(len(board[0])):
                cur = ''
                self.dfs(board, visited, r, c, trie, cur, ans)
        
        return list(ans)
    
    def dfs(self, board, visited, r, c, trie, cur, ans):
        if '#' in trie:
            ans.add(cur)
        
        if r < 0 or r >= len(board):
            return
        if c < 0 or c >= len(board[0]):
            return
        if visited[r][c]:
            return
        if board[r][c] not in trie:
            return

        letter = board[r][c]
        if letter in trie:
            cur += letter
            trie = trie[letter]

            visited[r][c] = True
            self.dfs(board, visited, r + 1, c, trie, cur, ans)
            self.dfs(board, visited, r - 1, c, trie, cur, ans)
            self.dfs(board, visited, r, c + 1, trie, cur, ans)
            self.dfs(board, visited, r, c - 1, trie, cur, ans)
            visited[r][c] = False