What is the time complexity of Word Search II?

The optimal solution has a time complexity of O(m * n * 4^L).

What data structures are used to solve Word Search II?

This problem uses Array, String, Backtracking, Trie, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Word Search II?

Insight 1: Using Trie data structure is crucial for efficient prefix matching. It allows us to quickly check if a given path in the board can potentially lead to any of the target words. Insight 2: Backtracking is essential for exploring different paths on the board to search for possible words. It involves recursively exploring adjacent cells while keeping track of the current word being formed.

Which companies ask LeetCode 212. Word Search II in interviews?

This problem is frequently asked at Airbnb, Aurora, Block, Capital One, Cisco and 11 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Word Search II - LeetCode 212 Solution

Word Search II - Complete Solution Guide

Word Search II is LeetCode problem 212, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an m x n board of characters and a list of strings words , 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. 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 2: Input: board = [["a","b"],["c

Detailed Explanation

The Word Search II problem asks us to find all words from a given list that exist within a 2D board of characters. Words must be formed by connecting adjacent cells (horizontally or vertically), and each cell can only be used once in a word. The input consists of the board (a 2D array of characters) and a list of words (strings). The output is a list of all words from the given list that are found on the board. The constraints specify the dimensions of the board, the length of the words, and the characters involved (lowercase English letters).

Solution Approach

The provided solution uses a combination of Trie data structure and Depth-First Search (DFS) with backtracking. First, a Trie is built using the given list of words. Then, a DFS is performed starting from each cell of the board. During the DFS, the current character is checked against the Trie. If the character exists as a child of the current Trie node, the search continues recursively in all four directions (up, down, left, right). When a complete word is found, it's added to the result list, and the word is marked as visited in the Trie to prevent duplicates. The board's cells are temporarily marked as visited using a special character to prevent reusing the same cell within a word.

Step-by-Step Algorithm

Step 1: Build a Trie data structure from the list of words. Each node in the Trie represents a character, and a path from the root to a node represents a prefix of a word. A flag is set at the end of each complete word.
Step 2: Iterate through each cell of the board. For each cell, check if the character in that cell is a child of the root node of the Trie. If it is, initiate a DFS starting from that cell.
Step 3: The DFS function takes the current row, column, and the current Trie node as input. It checks if the current Trie node represents the end of a word. If so, it adds the word to the result list and marks the word as visited (by setting the `word` field in the TrieNode to null).
Step 4: Mark the current cell as visited by temporarily changing its value to a special character (e.g., '#'). This prevents the same cell from being used multiple times in a single word.
Step 5: Recursively call the DFS function for all four adjacent cells (up, down, left, right), passing the corresponding child node of the current Trie node as the new current Trie node.
Step 6: After exploring all adjacent cells, backtrack by restoring the original value of the current cell and removing empty Trie nodes when possible.
Step 7: After iterating through all cells of the board, return the list of found words.

Key Insights

Insight 1: Using Trie data structure is crucial for efficient prefix matching. It allows us to quickly check if a given path in the board can potentially lead to any of the target words.
Insight 2: Backtracking is essential for exploring different paths on the board to search for possible words. It involves recursively exploring adjacent cells while keeping track of the current word being formed.
Insight 3: Optimizations like pruning the Trie during the search by removing empty child nodes and marking words as found after they are located prevent redundant computations and improve performance.

Complexity Analysis

Time Complexity: O(m * n * 4^L)

Space Complexity: O(N)

Topics

This problem involves: Array, String, Backtracking, Trie, Matrix.

Companies

Asked at: Airbnb, Aurora, Block, Capital One, Cisco, DoorDash, Google, Instacart, Karat, PayPal, Roblox, Snowflake, Two Sigma, Wix, Zoho, eBay.

Word Search II | LeetCode 212

Hard

Array String Backtracking Trie Matrix

Time: O(m * n * 4^L)Space: O(N)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    class TrieNode {
        Map<Character, TrieNode> children;
        String word;

        TrieNode() {
            this.children = new HashMap<>();
            this.word = null;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char char_ : word.toCharArray()) {
                if (!node.children.containsKey(char_)) {
                    node.children.put(char_, new TrieNode());
                }
                node = node.children.get(char_);
            }
            node.word = word;
        }

        int m = board.length;
        int n = board[0].length;
        List<String> result = new ArrayList<>();

        function dfs(int r, int c, TrieNode parent_node) {
            char char_ = board[r][c];
            TrieNode curr_node = parent_node.children.get(char_);

            if (curr_node == null) {
                return;
            }

            if (curr_node.word != null) {
                result.add(curr_node.word);
                curr_node.word = null;
            }

            board[r][c] = '#';

            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] direction : directions) {
                int nr = r + direction[0];
                int nc = c + direction[1];
                if (0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] != '#') {
                    dfs(nr, nc, curr_node);
                }
            }

            board[r][c] = char_;

            if (curr_node.children.isEmpty()) {
                parent_node.children.remove(char_);
            }
        }

        function dfs(int r, int c, TrieNode parent_node) {
            char char_ = board[r][c];
            TrieNode curr_node = parent_node.children.get(char_);

            if (curr_node == null) {
                return;
            }

            if (curr_node.word != null) {
                result.add(curr_node.word);
                curr_node.word = null;
            }

            board[r][c] = '#';

            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] direction : directions) {
                int nr = r + direction[0];
                int nc = c + direction[1];
                if (0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] != '#') {
                    dfs(nr, nc, curr_node);
                }
            }

            board[r][c] = char_;

            if (curr_node.children.isEmpty()) {
                parent_node.children.remove(char_);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (root.children.containsKey(board[i][j])) {
                    dfs(i, j, root);
                }
            }
        }

        return result;
    }

    private void dfs(int r, int c, char[][] board, TrieNode parent_node, List<String> result) {
        char char_ = board[r][c];
        TrieNode curr_node = parent_node.children.get(char_);

        if (curr_node == null) {
            return;
        }

        if (curr_node.word != null) {
            result.add(curr_node.word);
             curr_node.word = null;

        }

        board[r][c] = '#';

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] direction : directions) {
            int nr = r + direction[0];
            int nc = c + direction[1];
            if (0 <= nr && nr < board.length && 0 <= nc && nc < board[0].length && board[nr][nc] != '#') {
                dfs(nr, nc, board, curr_node, result);
            }
        }

        board[r][c] = char_;

        if (curr_node.children.isEmpty()) {
            parent_node.children.remove(char_);
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 212: Word Search II - Detailed explanation and solution approaches.

Topics

Array String Backtracking Trie Matrix

Companies

AirbnbAuroraBlockCapital OneCiscoDoorDashGoogleInstacart

Stats

Difficulty:Hard

Languages:4

Companies:16

Problem #:212

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Build a Trie data structure from the list of words. Each node in the Trie represents a character, and a path from the root to a node represents a prefix of a word. A flag is set at the end of each complete word.
2
Step 2: Iterate through each cell of the board. For each cell, check if the character in that cell is a child of the root node of the Trie. If it is, initiate a DFS starting from that cell.
3
Step 3: The DFS function takes the current row, column, and the current Trie node as input. It checks if the current Trie node represents the end of a word. If so, it adds the word to the result list and marks the word as visited (by setting the `word` field in the TrieNode to null).
4
Step 4: Mark the current cell as visited by temporarily changing its value to a special character (e.g., '#'). This prevents the same cell from being used multiple times in a single word.
5
Step 5: Recursively call the DFS function for all four adjacent cells (up, down, left, right), passing the corresponding child node of the current Trie node as the new current Trie node.
6
Step 6: After exploring all adjacent cells, backtrack by restoring the original value of the current cell and removing empty Trie nodes when possible.
7
Step 7: After iterating through all cells of the board, return the list of found words.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m * n * 4^L)

💾

Space Complexity

O(N)

📝

Why?

The time complexity arises from exploring all possible paths in the board. The `m * n` factor comes from starting the DFS from each cell in the board. The `4^L` factor is from the recursive DFS, branching out in 4 directions with a maximum path length of L. The space complexity is dominated by the Trie, which stores all the words.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Aho-Corasick Algorithm

The Aho-Corasick algorithm is a string searching algorithm that can efficiently find multiple patterns in a text. It can be used as an alternative to the Trie + DFS approach. It builds a state machine that can process the board character by character and identify matching words.

Time: O(m * n), where m is rows and n is columns of the board, after initial Aho-Corasick automaton construction. The automaton building takes O(sum of lengths of all words) time and space.Space: O(N), where N is the total length of all words (for building the Aho-Corasick automaton).

Trade-offs: Aho-Corasick can be more efficient when the number of words is very large, as it processes each cell of the board only once. However, the implementation is more complex.

✨

Key Insights

1Insight 1: Using Trie data structure is crucial for efficient prefix matching. It allows us to quickly check if a given path in the board can potentially lead to any of the target words.
2Insight 2: Backtracking is essential for exploring different paths on the board to search for possible words. It involves recursively exploring adjacent cells while keeping track of the current word being formed.
3Insight 3: Optimizations like pruning the Trie during the search by removing empty child nodes and marking words as found after they are located prevent redundant computations and improve performance.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty board or empty word list. The solution should handle these gracefully by returning an empty list, as there will be no words to find.
Edge case 2: Duplicate words in the input list. The Trie structure and the marking of words as visited (setting `word` to null) within the Trie ensure that duplicate words are not added to the result multiple times.
Edge case 3: Words with prefixes that are also in the word list. The solution correctly identifies both the prefix and the longer word if they both exist on the board.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using a Trie, leading to inefficient word matching. Without a Trie, each cell would need to be compared with every word in the list, leading to a very slow solution.

✗Common mistake 2: Not marking cells as visited during the DFS, resulting in infinite loops and incorrect results. This ensures that each cell is used only once within a single word.

✗Common mistake 3: Failing to remove empty Trie nodes after backtracking, leading to memory leaks or inefficient search later. Removing redundant branches is a key optimization.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Spell checking and auto-completion in text editors. The Trie data structure is used to store a dictionary of words, and the algorithm can be used to suggest possible words based on the user's input.

🏦Real-world scenario 2: Searching for gene sequences in a DNA sequence. The board represents the DNA sequence, and the words represent the gene sequences to be found. This allows identifying potential gene locations.

🎮Real-world scenario 3: Network intrusion detection systems. Detect malicious strings or patterns in network traffic using similar techniques to identify potential security threats.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Word Search II"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?