#212

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Word Search II

Solve the Word Search II problem using backtracking with pruning to find all words on a board of characters.

Problem Statement

In the Word Search II problem, you are given a 2D board of characters and a list of words. Your task is to return all the words from the list that can be formed by sequentially adjacent cells on the board. Adjacent cells can be horizontally or vertically neighboring, and each letter cell may only be used once per word.

To solve the problem, you need to efficiently search through the board using a backtracking approach. By starting from each letter and exploring all possible word paths, you must prune branches that do not lead to any valid words early on, optimizing your search to handle larger inputs.

Examples

Example 1

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Example details omitted.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"]

Output: []

Example details omitted.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution Approach

Backtracking Search with Trie

Use a Trie data structure to store all the words in the list, allowing for efficient prefix-based pruning during the search. Start at every board cell and explore potential words by backtracking, pruning whenever the current path does not lead to a valid word or prefix.

Pruning Unnecessary Searches

During the backtracking search, check if the current prefix matches any word in the Trie. If not, terminate the search early to avoid unnecessary exploration. This greatly speeds up the solution, especially when many words share prefixes.

Efficient Handling of Larger Inputs

Optimize the backtracking process by marking visited cells and cutting off branches as soon as possible. This allows the solution to scale with larger inputs, handling up to the problem's constraints of 30,000 words and board dimensions up to 12x12.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the Trie structure and the backtracking search. In the worst case, all cells of the board are visited for each word. Space complexity is influenced by the Trie storage and recursion depth during backtracking.

What Interviewers Usually Probe

The ability to optimize backtracking demonstrates an understanding of pruning and efficient search techniques.
Effective use of the Trie structure is a key indicator of solving this problem efficiently.
Understanding how to cut off unnecessary searches is critical for handling large test cases.

Common Pitfalls or Variants

Common pitfalls

Not pruning the search early enough, leading to excessive recursion and time complexity.
Forgetting to mark visited cells, which can cause revisiting and incorrect word formation.
Using a brute-force approach without considering optimizations for large inputs.

Follow-up variants

Word Search III with multiple boards and word lists.
Word Search II on an NxM grid with varying path constraints.
Multi-level Word Search where the words are split across different sections of the board.

FAQ

How does backtracking apply to Word Search II?

Backtracking is used to explore all potential paths on the board, trying to form each word. Early pruning is essential to stop unnecessary searches.

What is the role of Trie in Word Search II?

A Trie helps efficiently search for word prefixes, enabling quick pruning of invalid paths during the backtracking process.

What optimization is key for large inputs in Word Search II?

Pruning early and marking visited cells effectively are critical optimizations to ensure the solution handles large boards and word lists efficiently.

How can I improve performance for Word Search II?

By using Trie and backtracking with pruning, you can minimize unnecessary explorations and optimize the search process.

What are common mistakes in solving Word Search II?

Failing to prune searches early, not managing recursion depth, or not marking visited cells are common issues that lead to inefficient or incorrect solutions.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

class Trie:
    def __init__(self):
        self.children: List[Trie | None] = [None] * 26
        self.ref: int = -1

    def insert(self, w: str, ref: int):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.ref = ref


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        def dfs(node: Trie, i: int, j: int):
            idx = ord(board[i][j]) - ord('a')
            if node.children[idx] is None:
                return
            node = node.children[idx]
            if node.ref >= 0:
                ans.append(words[node.ref])
                node.ref = -1
            c = board[i][j]
            board[i][j] = '#'
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
                    dfs(node, x, y)
            board[i][j] = c

        tree = Trie()
        for i, w in enumerate(words):
            tree.insert(w, i)
        m, n = len(board), len(board[0])
        ans = []
        for i in range(m):
            for j in range(n):
                dfs(tree, i, j)
        return ans

Continue Practicing

#140 word break ii #79 word search #139 word break