212. Word Search II

212. Word Search II#

Difficulty: Hard

Link to Problem: To see the Word Search II problem on LeetCode, click here!

Given an m x n board of characters and a list of strings words, the task is to return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Constraints:

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

Probelm Explanation:#

To solve the “Word Search II” problem, you can use a Trie data structure and perform a depth-first search (DFS) on the board. Here’s a step-by-step approach to solve the problem:

Build a Trie from the given list of words:
- Create a Trie data structure to store all the words from the input list.
- For each word in the input list, insert it into the Trie, character by character. Make sure to mark the end of each word in the Trie.
Perform DFS on the board:
- Iterate through each cell (i, j) on the board.
- For each cell, start a DFS traversal from that cell to search for words.
- During the DFS traversal, maintain a current path string.
- At each cell, check if the current path string, concatenated with the character in the cell, matches any word prefix in the Trie. If it does, continue the DFS.
- If the current path string matches a word in the Trie, add it to the result.
Implement DFS with backtracking:
- During the DFS traversal, you will explore neighboring cells (horizontally and vertically) if they are within bounds and haven’t been visited before.
- To prevent revisiting the same cell within the same word, mark the cell as visited (e.g., change its character to a special character like ‘#’) before exploring it and restore its original character after the DFS traversal.
Return the result:
- After completing the DFS traversal for all cells on the board, you will have collected all the valid words in the result set.
- Convert the result set to a list and return it as the final output.

This approach efficiently finds all words on the board by utilizing the Trie data structure to prune unnecessary DFS paths and avoiding duplicate visits to the same cell within the same word. It ensures that each word is constructed from letters of sequentially adjacent cells without using the same letter cell more than once in a word.

Solution:#

Here’s a Python function to implement this algorithm:

# Define a TrieNode class to represent nodes in the Trie.
class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary to store child nodes.
        self.is_end_of_word = False  # Flag to mark the end of a word.

# Main function to find words on the board.
def findWords(board, words):
    # DFS function to search for words starting from a given cell.
    def dfs(node, i, j, path):
        char = board[i][j]  # Get the character at the current cell.
        curr_node = node.children.get(char)  # Find the corresponding Trie node.

        if not curr_node:
            return  # If no matching Trie node, stop the search.

        path += char  # Add the character to the current path.

        if curr_node.is_end_of_word:
            result.add(path)  # If the path matches a word, add it to the result.

        temp, board[i][j] = board[i][j], "#"  # Mark the cell as visited.

        # Explore neighboring cells (up, down, left, right).
        if i > 0:
            dfs(curr_node, i - 1, j, path)
        if i < m - 1:
            dfs(curr_node, i + 1, j, path)
        if j > 0:
            dfs(curr_node, i, j - 1, path)
        if j < n - 1:
            dfs(curr_node, i, j + 1, path)

        board[i][j] = temp  # Restore the cell's original character.

    # Function to build a Trie from the list of words.
    def buildTrie():
        root = TrieNode()  # Create a root node.
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()  # Create a new node if needed.
                node = node.children[char]
            node.is_end_of_word = True  # Mark the end of the word.
        return root

    m, n = len(board), len(board[0])  # Get the dimensions of the board.
    root = buildTrie()  # Build the Trie from the list of words.
    result = set()  # Use a set to store unique words found on the board.

    # Iterate through each cell on the board and start DFS from there.
    for i in range(m):
        for j in range(n):
            dfs(root, i, j, "")  # Start DFS from each cell on the board.

    return list(result)  # Convert the set to a list and return the result.

Explanation:#

The code solves the “Word Search II” problem, where you have a grid of characters and a list of words. The goal is to find all words from the list that can be constructed by traversing adjacent cells (horizontally or vertically) in the grid, without using the same cell more than once for a single word.

The code does the following:

Defines a TrieNode class to represent nodes in a Trie data structure. Each node has children (other characters in the word) and a flag to mark the end of a word.
Defines the findWords function, which takes the grid (board) and a list of words (words) as input.
Inside the findWords function, there is a dfs (depth-first search) function. This function is used to explore the grid starting from a specific cell. It checks if the current path matches any word in the Trie and adds it to the result if found.
The code also includes a buildTrie function that constructs a Trie data structure from the list of words. It iterates through each word, creating nodes for each character in the Trie and marking the end of words.
The dimensions of the grid are obtained (m x n).
A Trie is built using the buildTrie function.
A set called result is used to store unique words found in the grid.
The code iterates through each cell on the grid (using nested loops) and starts a DFS search from each cell.
During the DFS, it explores neighboring cells (up, down, left, right) if they haven’t been visited before and if the current path matches a prefix in the Trie.
When a word is found during the DFS traversal, it is added to the result set.
The grid cell is marked as visited during the DFS by changing its character to “#”, and it is restored to its original character after the DFS traversal.
Finally, the set of unique words found is converted to a list and returned as the output.

The code effectively uses a Trie data structure to optimize the search and ensures that each word is constructed from adjacent cells without reusing the same cell for the same word.

Test cases:#

Here’s how you can use this solution:

# Example 1: 

board1 = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words1 = ["oath","pea","eat","rain"]
print(findWords(board1, words1))  # Output: ["eat", "oath"]

['eat', 'oath']

# Example 2

board2 = [["a","b"],["c","d"]]
words2 = ["abcb"]
print(findWords(board2, words2))  # Output: []

[]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

Building the Trie (buildTrie function):
- Suppose there are N words in the input list, and the average length of a word is L.
- Building the Trie takes O(N * L) time, as we iterate through each word and insert each character into the Trie.
DFS Traversal (dfs function):
- In the worst case, the DFS function explores all possible paths in the grid.
- The maximum number of recursive calls for each cell is 4 (up, down, left, right).
- The maximum depth of the DFS is limited by the length of the longest word in the Trie, which is at most L.
- Therefore, the DFS traversal for each cell takes \(O(4^L)\) time.
Iterating Through the Grid (findWords function):
- In the worst case, we iterate through all m rows and n columns in the grid.
- For each cell, we start a DFS traversal.
- Therefore, iterating through the entire grid takes \(O(m * n * 4^L)\) time.

Overall, the time complexity of the code is \(O(N * L + m * n * 4^L)\).

Space Complexity:

Trie Data Structure:
- The space required to store the Trie depends on the number of unique characters in all the words.
- In the worst case, where all words are unique and have no common prefixes, the space complexity of the Trie is O(N * L).
- In practice, it may be less if there are common prefixes among words.
DFS Stack (Recursive Calls):
- The depth of the recursive call stack during DFS is at most L, where L is the length of the longest word in the Trie.
- Therefore, the space complexity for the recursive call stack is O(L).
Result Set (result set):
- The space used to store the result set depends on the number of valid words found in the grid.
- In the worst case, when all words are found, the space complexity of the result set is O(N * L).

Overall, the space complexity of the code is O(N * L) for the Trie and O(L) for the recursive call stack.

In summary, the time complexity is dominated by the DFS traversal and is influenced by the number of words, their lengths, and the size of the grid. The space complexity is mainly determined by the Trie structure and the recursive call stack depth during DFS.

Challenging Exercises:#

Word Search Paths: Extend the basic word search exercise to find all possible paths (sequences of cells) that spell out a given word on the board. Return a list of paths if the word can be formed, otherwise an empty list.
Reverse Word Search: Modify the code to search for words in reverse order on the board. Given a 2D grid of characters and a list of words, find all words from the list that can be formed by traversing the board in reverse (right to left, bottom to top, etc.).