212 Word Search II

https://leetcode.com/problems/word-search-ii/

solution

• trie

# https://leetcode.com/problems/word-search-ii/solutions/59790/python-dfs-solution-directly-use-trie-implemented/

class Trie:
    def __init__(self):
        self.children = collections.defaultdict(Trie)
        self.word = ""  # 直接在结尾的node标记整个word

    def insert(self, word):  # 插入一个单词
        cur = self  # 起点从最外面开始
        for c in word:
            cur = cur.children[c]
        # cur.is_word = True
        cur.word = word

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = Trie()
        for word in words:
            trie.insert(word)
        
        ans = set()
        m = len(board)
        n = len(board[0])
        for i in range(m):
            for j in range(n):
                self.dfs(board, i, j, trie, ans)
        return list(ans)
    
    def dfs(self, board, i, j, trie, ans):        
        char = board[i][j]
        cur = trie.children[char]

        if cur.word:
            ans.add(cur.word)
        
        board[i][j] = '#'
        for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:  # 每一个位置可以朝四个方向查找, 如果新的可以从trie中找到则继续递归
            new_i = i + dx
            new_j = j + dy
            if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]) and board[new_i][new_j] in cur.children:
                self.dfs(board, new_i, new_j, cur, ans)
        
        board[i][j] = char

follow up

79. Word Search