Word Search II
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.
Constraints:
- 1 <= board.length <= 12
- 1 <= board[i].length <= 12
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- board and words consists of only lowercase English letters
Examples:
Input: [["o","a","a","n"],"o","i","n"],"ean"],[["p","e","a","r"],"o","a","a","n"],"rain"],[["m","e","a"],"o","a","o","i","n"],"me"]
Output: ["oath","pea","eat","rain"]
Explanation: The words can be found as follows: o-a-t-h, p-e-a, e-a-t, r-a-i-n
Solutions
Trie and Depth-First Search
The solution uses a Trie data structure to store the words and then uses depth-first search to find all words in the board. The Trie is constructed by iterating over each word and adding each character to the Trie. Then, for each cell in the board, we start a depth-first search from that cell and explore all possible words that can be formed from that cell. If a word is found, it is added to the result list and the word is removed from the Trie to avoid duplicates.
class TrieNode:
def __init__(self):
self.children = {}
self.end = None
class Solution:
def findWords(self, board, words):
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end = word
res, visit = set(), set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(i, j, node):
if node.end:
res.add(node.end)
node.end = None
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or (i, j) in visit or board[i][j] not in node.children:
return
visit.add((i, j))
temp = board[i][j]
board[i][j] = '#'
for dx, dy in directions:
dfs(i + dx, j + dy, node.children[temp])
board[i][j] = temp
visit.remove((i, j))
for i in range(len(board)):
for j in range(len(board[0])):
dfs(i, j, root)
return list(res)Follow-up:
How would you optimize the solution to handle a large number of words?
