Word search II#
Practice Link#
Description#
- Given a 2D board and a list of words from the dictionary, find all words in the board.
- Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring.
- The same letter cell may not be used more than once in a word.
Note:
- All inputs are consist of lowercase letters a-z.
- The values of words are distinct.
Example#
1Input:
2board = [
3 ['o','a','a','n'],
4 ['e','t','a','e'],
5 ['i','h','k','r'],
6 ['i','f','l','v']
7]
8words = ["oath","pea","eat","rain"]
9
10Output: ["eat","oath"]Python Solution#
1import collections
2
3
4class TrieNode():
5 def __init__(self):
6 self.children = collections.defaultdict(TrieNode)
7 self.isWord = False
8
9
10class Trie():
11 def __init__(self):
12 self.root = TrieNode()
13
14 def insert(self, word):
15 node = self.root
16 for w in word:
17 node = node.children[w]
18 node.isWord = True
19
20 def search(self, word):
21 node = self.root
22 for w in word:
23 node = node.children.get(w)
24 if not node:
25 return False
26 return node.isWord
27
28
29class Solution(object):
30 def findWords(self, board, words):
31 res = []
32 trie = Trie()
33 node = trie.root
34 for w in words:
35 trie.insert(w)
36 for i in range(len(board)):
37 for j in range(len(board[0])):
38 self.dfs(board, node, i, j, "", res)
39 return res
40
41 def dfs(self, board, node, i, j, path, res):
42 if node.isWord:
43 res.append(path)
44 node.isWord = False
45 if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
46 return
47 tmp = board[i][j]
48 node = node.children.get(tmp)
49 if not node:
50 return
51 board[i][j] = "#"
52 self.dfs(board, node, i + 1, j, path + tmp, res)
53 self.dfs(board, node, i - 1, j, path + tmp, res)
54 self.dfs(board, node, i, j - 1, path + tmp, res)
55 self.dfs(board, node, i, j + 1, path + tmp, res)
56 board[i][j] = tmp