LeetCode 单词搜索II题解

LeetCode 单词搜索II题解题目描述给定一个二维字符网格和一个字符串数组找出所有在网格中出现的单词。示例输入board [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]],words [oath,pea,eat,rain]输出[eat,oath]解题思路方法字典树 DFS思路首先将所有单词插入字典树。然后使用 DFS 遍历网格对于每个单元格从字典树中查找以该单元格字符开头的单词。如果找到了一个单词将其加入结果列表并标记为已访问。复杂度分析时间复杂度O(m * n * 4^L)。空间复杂度O(L)。代码实现class TrieNode: def __init__(self): self.children {} self.word None class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for char in word: if char not in node.children: node.children[char] TrieNode() node node.children[char] node.word word def find_words(board, words): trie Trie() for word in words: trie.insert(word) result [] m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] def dfs(i, j, node): if visited[i][j]: return char board[i][j] if char not in node.children: return node node.children[char] if node.word: result.append(node.word) node.word None visited[i][j] True for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: ni, nj i di, j dj if 0 ni m and 0 nj n: dfs(ni, nj, node) visited[i][j] False for i in range(m): for j in range(n): dfs(i, j, trie.root) return result # 测试 def test_find_words(): board [[o,a,a,n],[e,t,a,e],[i,h,k,r],[i,f,l,v]] words [oath,pea,eat,rain] print(find_words(board, words)) # 输出[eat, oath] if __name__ __main__: test_find_words()总结单词搜索II是字典树和 DFS 的典型应用将所有单词插入字典树然后遍历网格查找单词。