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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which data structure is used in a depth first search?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

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

1from typing import List
2
3class Trie:
4    def __init__(self):
5        # Initializing the children with an array of 26 Trie nodes representing each character of the alphabet.
6        self.children: List[Trie | None] = [None] * 26
7        # Reference to the index of the word in the words list, -1 if it's not a complete word.
8        self.ref: int = -1
9
10    def insert(self, word: str, ref: int):
11        node = self
12        # Insert each character of the word in the Trie.
13        for char in word:
14            index = ord(char) - ord('a')
15            # If the child node for this character does not exist, create it.
16            if node.children[index] is None:
17                node.children[index] = Trie()
18            node = node.children[index]
19        # Set the reference index for the last character node to the word's index in the input list.
20        node.ref = ref
21
22
23class Solution:
24    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
25        def dfs(node: Trie, i: int, j: int):
26            # Conducts a depth-first search starting from board[i][j].
27            index = ord(board[i][j]) - ord('a')
28            # If there's no child node for this character, return.
29            if node.children[index] is None:
30                return
31            node = node.children[index]
32            # If this node is a complete word, add to the answer list and mark it as visited.
33            if node.ref >= 0:
34                ans.append(words[node.ref])
35                node.ref = -1
36            # Temporarily mark the board position as visited by replacing the character with '#'.
37            temp_char = board[i][j]
38            board[i][j] = '#'
39            # Visit all neighbors (up, right, down, left).
40            for x_offset, y_offset in zip(*[iter([-1, 0, 1, 0, -1])] * 2):
41                x, y = i + x_offset, j + y_offset
42                # If the new position is within bounds and not visited, continue DFS.
43                if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
44                    dfs(node, x, y)
45            # Restore the original character after visiting neighbors.
46            board[i][j] = temp_char
47
48        # Initialize the Trie and fill it with the words.
49        trie_root = Trie()
50        for index, word in enumerate(words):
51            trie_root.insert(word, index)
52        # Get the dimensions of the board.
53        m, n = len(board), len(board[0])
54        # List to store the answer words.
55        ans = []
56        # Loop through each cell in the board and start DFS if possible.
57        for i in range(m):
58            for j in range(n):
59                dfs(trie_root, i, j)
60        return ans
61
62# The `List[Trie | None]` syntax requires at least Python 3.10, where the union pipe operator was introduced.
63# For earlier versions of Python, it would be List[Optional[Trie]] with from typing import Optional.
64
1class Trie {
2    // Trie node array to hold child nodes.
3    Trie[] children = new Trie[26];
4    // Reference index for words array in Solution class (-1 means no reference).
5    int reference = -1;
6
7    // Method to insert a word into the trie
8    public void insert(String word, int reference) {
9        Trie node = this;
10        for (int i = 0; i < word.length(); i++) {
11            // Calculate index of the character 'a' through 'z'
12            int characterIndex = word.charAt(i) - 'a';
13            // If the character node does not exist, create it
14            if (node.children[characterIndex] == null) {
15                node.children[characterIndex] = new Trie();
16            }
17            // Move to the child node
18            node = node.children[characterIndex];
19        }
20        // At the end of insertion, set the reference index
21        node.reference = reference;
22    }
23}
24
25class Solution {
26    private char[][] board;
27    private String[] words;
28    private List<String> foundWords = new ArrayList<>();
29
30    // Function to search words in the given board
31    public List<String> findWords(char[][] board, String[] words) {
32        this.board = board;
33        this.words = words;
34        Trie trie = new Trie();
35        // Insert all words into the Trie
36        for (int i = 0; i < words.length; i++) {
37            trie.insert(words[i], i);
38        }
39        // Board dimensions
40        int rowCount = board.length;
41        int colCount = board[0].length;
42        // Start DFS from every cell
43        for (int i = 0; i < rowCount; i++) {
44            for (int j = 0; j < colCount; j++) {
45                dfs(trie, i, j);
46            }
47        }
48        return foundWords;
49    }
50
51    // Helper method to perform DFS on the board
52    private void dfs(Trie node, int i, int j) {
53        int charIndex = board[i][j] - 'a';
54        // If there is no child node corresponding to the current board character, prune the search
55        if (node.children[charIndex] == null) {
56            return;
57        }
58        // Move to the corresponding child node
59        node = node.children[charIndex];
60        // If the node holds a word (reference is not -1), add it to our answer
61        if (node.reference != -1) {
62            foundWords.add(words[node.reference]);
63            // To avoid duplicate entries, reset the reference to -1
64            node.reference = -1;
65        }
66        // Mark the board character as visited
67        char tempChar = board[i][j];
68        board[i][j] = '#';
69        // Array to explore the 4 adjacent directions (up, right, down, left)
70        int[] directions = {-1, 0, 1, 0, -1};
71        for (int k = 0; k < 4; k++) {
72            int newRow = i + directions[k];
73            int newCol = j + directions[k + 1];
74            // Check the boundaries and if the new position is not visited
75            if (newRow >= 0 && newRow < rowCount && newCol >= 0 && newCol < colCount && board[newRow][newCol] != '#') {
76                dfs(node, newRow, newCol);
77            }
78        }
79        // Unmark the board character
80        board[i][j] = tempChar;
81    }
82}
83
1#include <vector>
2#include <string>
3#include <functional>
4
5using namespace std;
6
7class Trie {
8private:
9    vector<Trie*> children; // Vector holding pointers to child Trie nodes
10    int wordIndex;          // Stores the index of the word in the 'words' vector if the end of a word is reached
11
12public:
13    // Constructor initializes Trie node
14    Trie()
15        : children(26, nullptr), wordIndex(-1) {}
16
17    // Inserts a word into the Trie with a reference index
18    void insert(const string& word, int index) {
19        Trie* node = this;
20        for (char c : word) {
21            c -= 'a';
22            if (!node->children[c]) {
23                node->children[c] = new Trie();
24            }
25            node = node->children[c];
26        }
27        node->wordIndex = index;
28    }
29};
30
31class Solution {
32public:
33    // Function to find words on the board given a list of words
34    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
35        Trie* trieRoot = new Trie();
36        // Construct trie from words list
37        for (int i = 0; i < words.size(); ++i) {
38            trieRoot->insert(words[i], i);
39        }
40        vector<string> foundWords;
41        int rows = board.size(), cols = board[0].size();
42
43        // Depth-first search in the board starting from (i, j) position
44        function<void(Trie*, int, int)> dfs = [&](Trie* node, int i, int j) {
45            int charIndex = board[i][j] - 'a';
46            if (!node->children[charIndex]) {
47                return; // Early return if no child exists for the current character
48            }
49            node = node->children[charIndex];
50            if (node->wordIndex != -1) {
51                foundWords.emplace_back(words[node->wordIndex]);
52                node->wordIndex = -1; // Avoid duplicate entries in the results
53            }
54            int directions[5] = {-1, 0, 1, 0, -1}; // Up, Right, Down, Left
55            char tempChar = board[i][j];           // Save current character
56            board[i][j] = '#';                     // Mark current cell as visited
57            for (int k = 0; k < 4; ++k) { // Explore neighbors
58                int x = i + directions[k], y = j + directions[k + 1];
59                if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] != '#') {
60                    dfs(node, x, y);
61                }
62            }
63            board[i][j] = tempChar; // Reset the current cell to its original value
64        };
65
66        // Start DFS from every cell in the board
67        for (int i = 0; i < rows; ++i) {
68            for (int j = 0; j < cols; ++j) {
69                dfs(trieRoot, i, j);
70            }
71        }
72        return foundWords; // Return all found words
73    }
74};
75
1// Define the trie node structure globally.
2let trieNodes: { children: (number | null)[]; ref: number }[] = [];
3let nodeIdCounter = 0;
4
5// Function to create a new trie node.
6function createTrieNode(): number {
7    const newNodeId = nodeIdCounter++;
8    trieNodes[newNodeId] = { children: Array(26).fill(null), ref: -1 };
9    return newNodeId;
10}
11
12// Function to insert a word into the trie.
13function insertIntoTrie(word: string, ref: number): void {
14    let nodeId = 0;
15    for (const char of word) {
16        const index = char.charCodeAt(0) - 97;
17        if (trieNodes[nodeId].children[index] === null) {
18            trieNodes[nodeId].children[index] = createTrieNode();
19        }
20        nodeId = trieNodes[nodeId].children[index] as number;
21    }
22    trieNodes[nodeId].ref = ref;
23}
24
25// Function to find words on the board that exist in the trie.
26function findWords(board: string[][], words: string[]): string[] {
27    // Reset the global trie nodes.
28    trieNodes = [];
29    nodeIdCounter = 0;
30    createTrieNode(); // Create the root node.
31
32    // Insert each word from the list into the trie.
33    words.forEach((word, index) => insertIntoTrie(word, index));
34
35    const rows = board.length;
36    const cols = board[0].length;
37    const foundWords: string[] = [];
38
39    // Define directions for adjacent cells: up, right, down, left.
40    const directions: number[] = [-1, 0, 1, 0, -1];
41
42    // Depth-first search function to search for words in the board.
43    function dfs(nodeId: number, x: number, y: number, curWord: string): void {
44        const charIndex = board[x][y].charCodeAt(0) - 97;
45        const nextNodeId = trieNodes[nodeId].children[charIndex];
46        if (nextNodeId === null) {
47            return;
48        }
49
50        curWord += board[x][y];
51
52        if (trieNodes[nextNodeId].ref != -1) {
53            foundWords.push(words[trieNodes[nextNodeId].ref]);
54            trieNodes[nextNodeId].ref = -1; // Mark the word as discovered.
55        }
56
57        const originalChar = board[x][y];
58        board[x][y] = '#'; // Mark the current position as visited.
59
60        // Explore all possible directions.
61        for (let i = 0; i < 4; ++i) {
62            const newX = x + directions[i];
63            const newY = y + directions[i + 1];
64
65            // Continue DFS if the new position is within boundaries and not visited.
66            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && board[newX][newY] !== '#') {
67                dfs(nextNodeId, newX, newY, curWord);
68            }
69        }
70
71        board[x][y] = originalChar; // Reset the position back to original state.
72    }
73
74    // Iterate over the entire board to start DFS from each cell.
75    for (let i = 0; i < rows; ++i) {
76        for (let j = 0; j < cols; ++j) {
77            dfs(0, i, j, '');
78        }
79    }
80
81    return foundWords;
82}
83
Not Sure What to Study? Take the 2-min Quiz:

Which data structure is used to implement priority queue?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«