How do you solve Word Search II on LeetCode?

Word Search II (LeetCode #212) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * k * m * 4^m) time complexity and O(n) space complexity. Key insight: Using a Trie allows for efficient prefix searching, which is crucial in this problem.

What is the brute force solution for Word Search II?

The brute force approach for Word Search II is Brute Force, with O(n² * k * 4^k) time complexity and O(k) space complexity. The brute-force approach involves checking every possible path on the board for each word. This means exploring all adjacent cells recursively until we either find the word or exhaust all possibilities. The optimal Optimal Solution approach improves this to O(n * k * m * 4^m).

What algorithm or data structure is used to solve Word Search II?

Word Search II uses the following concepts: Array, String, Backtracking, Trie, Matrix. The recommended patterns to study are: Trie, Backtracking.

What are the interview tips for Word Search II?

Explain your thought process clearly while coding; it shows your understanding. Discuss the trade-offs of different approaches before jumping into coding. Practice writing Trie data structure as it is commonly used in string-related problems.

What are common mistakes when solving Word Search II?

Not handling the visited cells properly, leading to incorrect results. Failing to check for prefixes in the Trie, resulting in unnecessary searches.

#212

Word Search II

Hard

ArrayStringBacktrackingTrieMatrixTrieBacktracking

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n² * k * 4^k)	O(n * k * m * 4^m)
Space	O(k)	O(n)

💡

Intuition

Time O(n * k * m * 4^m)Space O(n)

The optimal solution uses a Trie to store the words and a backtracking approach to search for them on the board. This significantly reduces the number of unnecessary searches by allowing early termination when a prefix is not found.

⚙️

Algorithm

3 steps

1Step 1: Build a Trie from the list of words.
2Step 2: For each cell in the board, start a backtracking search if the cell matches the first character of any word in the Trie.
3Step 3: If a complete word is found during the search, add it to the result set.

solution.py39 lines

1# Full working Python code
2class TrieNode:
3    def __init__(self):
4        self.children = {}
5        self.is_end_of_word = False
6
7class Solution:
8    def findWords(self, board, words):
9        self.result = set()
10        self.trie = TrieNode()
11        for word in words:
12            self.insert(word)
13        for i in range(len(board)):
14            for j in range(len(board[0])):
15                self.backtrack(board, i, j, self.trie, '')
16        return list(self.result)
17
18    def insert(self, word):
19        node = self.trie
20        for char in word:
21            if char not in node.children:
22                node.children[char] = TrieNode()
23            node = node.children[char]
24        node.is_end_of_word = True
25
26    def backtrack(self, board, x, y, node, path):
27        if node.is_end_of_word:
28            self.result.add(path)
29            node.is_end_of_word = False  # Prevent duplicates
30        if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] == '#':
31            return
32        char = board[x][y]
33        if char not in node.children:
34            return
35        board[x][y] = '#'  # Mark as visited
36        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
37            self.backtrack(board, x + dx, y + dy, node.children[char], path + char)
38        board[x][y] = char  # Restore the cell
39

ℹ

Complexity note: The time complexity is reduced because we only explore valid paths that match prefixes in the Trie, avoiding unnecessary searches. The space complexity is mainly due to the Trie structure.

1Using a Trie allows for efficient prefix searching, which is crucial in this problem.
2Backtracking can be optimized by marking cells as visited and restoring them after exploring.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.