212. Word Search II

Problem Description

In this LeetCode problem, we are given a 2D board of characters (i.e., a grid of letters) and a list of strings called words. Our objective is to find out which words from the list can be formed using the characters on the board. A word can be constructed by linking letters that are adjacent to each other either horizontally or vertically. One additional constraint is that each letter on the board can only be used once for the formation of a word.

Intuition

The intuition behind the solution to this problem is to use a backtracking algorithm to explore all the possible paths on the board and see if they match any of the provided words. However, doing this naively would be highly inefficient, as we would need to check against all words every time we explore a path. To optimize this process, we can use a data structure known as a Trie, which is an efficient way to store a set of strings where each node represents a character and indicates possible continuations of the prefix formed by the characters from the root to that node.

By inserting all the words into the Trie, we can quickly determine if a sequence of characters encountered during the depth-first search (DFS) backtracking matches a word in the Trie. Each node in the Trie can also be flagged to indicate the end of one of the input words, so when we reach such a node during the DFS, we know that we have found a valid word. We then add that word to the answer list.

The backtracking function dfs is then used to explore the board. Starting from each cell, we try to explore its neighboring cells (up, down, left, right). If the next cell continues a prefix in the Trie, we move to it; otherwise, we prune the exploration. To avoid revisiting cells, we mark a cell as visited by replacing its character with a placeholder and revert it back after the exploration. The DFS ensures that we explore all possible words that can be constructed from each starting cell. After the DFS is complete for all starting cells, we'd have collected all words found on the board in the ans list, which we return as the solution to the problem.

Learn more about Trie and Backtracking patterns.

Solution Approach

The solution approach involves several key steps and employs a combination of algorithms and data structures:

1. Trie Construction: We first construct a Trie data structure that will store the list of words we're trying to find on the board. Each node represents a character, and a path from the root to a leaf node spells out a word. With the insert method, we add each word into the Trie, and we also keep a reference index which points to the word's position in the original list. This is important as it allows us to directly add the word to the answer list (denoted as ans) when we find it on the board.

2. DFS Algorithm: We use a Depth First Search (DFS) backtracking algorithm (dfs function) to explore the board. Starting from each cell, we move to adjacent cells (up, down, left, right), but only if the continuation forms a prefix of any word in the Trie. By doing so, we efficiently avoid unnecessary paths that do not lead to any word in the list.

3. Backtracking: A key part of the DFS algorithm is backtracking; we mark the current cell so that we won't use it again in the current path by temporarily changing its value to a placeholder character (#). Once we finish exploring all possible paths from that cell, we restore its original value.

4. Checking for Words: During the exploration, when we reach a Trie node that signals the end of a word (i.e., node.ref >= 0), it means we have found a complete word on the board. We add this word to the ans. To prevent the same word from being added multiple times, we invalidate the reference by setting node.ref to -1.

5. Exploration: The actual DFS exploration is triggered for every cell on the board, using nested loops. From each cell, the dfs function is called which will explore all valid paths that can be formed starting with that cell.

Here are the core parts of the solution highlighted with some details:

• The dfs function takes a Trie node and board indices i and j. If we reach a Trie node without children (i.e., no more possible continuations), or out of the board bounds, the recursion ends.
• The for loop within dfs goes through the 4 possible directions using the pairwise helper function. For each adjacent cell, it makes a recursive call to dfs if the next cell hasn't been visited (not marked with #).
• The for loop in the Solution.findWords method iterates over all cells of the board to start the DFS search.

By combining the Trie data structure with the DFS backtracking algorithm, we efficiently search through the board for all given words without redundantly checking the same paths or comparing with the entire words list repeatedly.

Example Walkthrough

Let's take a small example to illustrate the solution approach. Imagine we have the following board:

1[
2  ['o','a','a','n'],
3  ['e','t','a','e'],
4  ['i','h','k','r'],
5  ['i','f','l','v']
6]

And the words list: ["oath", "pea", "eat", "rain"].

First, we build the Trie with the given words. The Trie after the insertion of the words will loosely look like a tree with paths corresponding to letters of each word. For simplicity in illustration:

1root
2 ├── o
3 │   └── a
4 │       └── t
5 │           └── h (*)
6 ├── p
7 │   └── e
8 │       └── a (*)
9 ├── e
10 │   └── a
11 │       └── t (*)
12 └── r
13     └── a
14         └── i
15             └── n (*)

Here, (*) represents a node that marks the end of a word in the Trie.

Now, we begin the DFS exploration using the dfs function from each cell in the board. Let's walk through finding the word "oath":

1. Starting at cell board[0][0] with the letter 'o', we see that 'o' is the start of a word ("oath") in the Trie. We proceed with this path.

2. From 'o', we can go right to the letter 'a' at board[0][1]. 'oa' is a prefix in the Trie, so we continue.

3. Next, we move down from 'a' to 't' at board[1][1]. 'oat' is still a valid prefix. We move on.

4. Finally, from 't', we move right to the letter 'h' at board[1][2]. 'oath' is found in the Trie, and it's a complete word indicated by the end marker (*). We add "oath" to the ans list.

We continue this process for all other starting cells and directions to find all matches. Notably:

• The sequence 'e', 'a', 't' can be constructed starting from board[1][0], so "eat" will also be found and added to the ans list.
• "pea" and "rain" will not be found because they cannot be constructed from the board as per the given adjacency rules.

Our final ans list will have the words ["oath", "eat"] as those are the only ones that can be formed from the board given the rules.

Throughout this process, the DFS backtracking ensures that if we go down a path that doesn't lead to a word, we backtrack and try different paths. For example, after trying 'o' -> 'a' -> 't', if we go up and reach 'n' at board[0][3], this is not a word or a valid prefix, so we backtrack to 't' and try a different direction. By marking cells as visited, we avoid cycles and repeating cells within the same path, and by using the Trie, we are able to quickly dismiss invalid paths, leading to an efficient solution.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of this code can be broken down into two major parts: building the Trie and performing the depth-first search (DFS).

1. Building the Trie: For each word in words, we insert each character into the Trie. If we assume the average length of a word is L and there are W words, this operation is O(W * L).

2. Depth-First Search (DFS): The DFS is performed for each cell in the board, which has M rows and N columns. In the worst case, if the Trie contains a path that matches all the cells in the board, we would explore 4 directions every time (except when on the border of the board). Nonetheless, we have a backtracking mechanism that marks cells as visited by replacing their content with '#', preventing revisits.

   However, since we "clear" a word from the Trie as soon as we encounter it (node.ref = -1), the impact of finding the same word multiple times is negated, effectively pruning the search space. Thus, for a cell, the DFS could potentially visit all the cells once, making it O(M * N) per starting cell, but due to prevents of redundant searches, it would approximate O(M * N).

   Combining this with all starting points yields O(M * N * M * N).

Space Complexity

1. Trie: The space used by the Trie can go up to O(W * L), considering all words are stored without overlap. In the case of significant overlap (e.g., prefixes are shared), the space used would be less.

2. DFS Stack Space: The recursive implementation of DFS adds a significant space overhead due to the stack. In the worst case, the stack space can go up to O(M * N) if the DFS goes through all cells.

3. Output List: The space for the ans list is O(W), since we can have at most W words on the board.

Combining these factors, the total space complexity is O(W * L + M * N + W), which simplifies to O(W * L + M * N) since typically, the number of words and their length may not necessarily be smaller than the size of the board.

Therefore, considering both worst-case scenarios:

• The overall time complexity of the solution is O(W * L + M^2 * N^2).
• The overall space complexity of the solution is O(W * L + M * N).

Learn more about how to find time and space complexity quickly using problem constraints.