What is the time complexity of Word Search?

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

What data structures are used to solve Word Search?

This problem uses Array, String, Backtracking, Depth-First Search, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Word Search?

Insight 1: Backtracking is suitable because we need to explore all possible paths from each cell in the grid to see if any path matches the given word. If a path doesn't work, we need to backtrack and try a different path. Insight 2: A key optimization is to temporarily mark visited cells during the backtracking search to avoid cycles and using the same cell multiple times.

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

Word Search - LeetCode 79 Solution

Q: Which companies ask LeetCode 79. Word Search in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Arista Networks, Atlassian and 29 more companies.

Word Search - Complete Solution Guide

Word Search is LeetCode problem 79, a Medium 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 grid of characters board and a string word , return true if word exists in the grid . The word can 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. Example 1: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true Example 2: Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

Detailed Explanation

The problem asks us to determine if a given word can be found within a 2D grid (board) of characters. The word must be formed by sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. A cell can only be used once within the formation of the word.

Solution Approach

The solution uses a backtracking (Depth-First Search - DFS) approach to explore all possible paths in the grid. The main function `exist` iterates through each cell in the grid and calls a helper function `backtrack` to check if the word can be formed starting from that cell. The `backtrack` function recursively explores adjacent cells, checking if their characters match the next character in the word. To avoid revisiting the same cell, the current cell's character is temporarily replaced with a special character ('#'). After the exploration, the original character is restored to allow other paths to be explored correctly.

Step-by-Step Algorithm

Step 1: Iterate through each cell (r, c) of the board.
Step 2: For each cell, call the backtrack function with the starting position (r, c) and index 0 (start of the word).
Step 3: The backtrack function checks the base cases: If the index equals the word's length, it means the entire word has been found, so return true. If the current position (r, c) is out of bounds or the character at the board[r][c] does not match the character at word[index], return false.
Step 4: If the base cases are not met, temporarily mark the current cell as visited by replacing its character with '#'.
Step 5: Recursively call the backtrack function for all four adjacent cells (up, down, left, right) with the index incremented by 1.
Step 6: If any of the recursive calls return true (meaning the word was found along that path), return true.
Step 7: Before returning, restore the original character of the current cell to the board.
Step 8: If the backtrack function returns false for all starting cells, it means the word was not found in the board, so return false.

Key Insights

Insight 1: Backtracking is suitable because we need to explore all possible paths from each cell in the grid to see if any path matches the given word. If a path doesn't work, we need to backtrack and try a different path.
Insight 2: A key optimization is to temporarily mark visited cells during the backtracking search to avoid cycles and using the same cell multiple times.
Insight 3: The search process needs to start from every cell in the grid because the word can potentially start at any location.

Complexity Analysis

Time Complexity: O(M * N * 4^L)

Space Complexity: O(L)

Topics

This problem involves: Array, String, Backtracking, Depth-First Search, Matrix.

Companies

Asked at: Adobe, Amazon, Apple, Arista Networks, Atlassian, Bloomberg, Capital One, Cisco, Citadel, Epic Systems, Faire, FreshWorks, Goldman Sachs, Grammarly, Karat, MakeMyTrip, Meta, Microsoft, Morgan Stanley, Netflix, Oracle, PayPal, Paytm, Samsung, Snap, TikTok, Uber, Visa, Walmart Labs, Whatnot, Wix, Zepto, Zoho, tcs.

Word Search | LeetCode 79

Medium

Array String Backtracking Depth-First Search Matrix

Time: O(M * N * 4^L)Space: O(L)

Solution Code

Available in:

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (backtrack(board, r, c, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean backtrack(char[][] board, int r, int c, String word, int index) {
        if (index == word.length()) {
            return true;
        }

        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(index)) {
            return false;
        }

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

        boolean found = (backtrack(board, r + 1, c, word, index + 1) ||
                         backtrack(board, r - 1, c, word, index + 1) ||
                         backtrack(board, r, c + 1, word, index + 1) ||
                         backtrack(board, r, c - 1, word, index + 1));

        board[r][c] = original_char;

        return found;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 79: Word Search - Detailed explanation and solution approaches.

Topics

Array String Backtracking Depth-First Search Matrix

Companies

AdobeAmazonAppleArista NetworksAtlassianBloombergCapital OneCisco

Stats

Difficulty:Medium

Languages:4

Companies:34

Problem #:79

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

8 steps

1
Step 1: Iterate through each cell (r, c) of the board.
2
Step 2: For each cell, call the backtrack function with the starting position (r, c) and index 0 (start of the word).
3
Step 3: The backtrack function checks the base cases: If the index equals the word's length, it means the entire word has been found, so return true. If the current position (r, c) is out of bounds or the character at the board[r][c] does not match the character at word[index], return false.
4
Step 4: If the base cases are not met, temporarily mark the current cell as visited by replacing its character with '#'.
5
Step 5: Recursively call the backtrack function for all four adjacent cells (up, down, left, right) with the index incremented by 1.
6
Step 6: If any of the recursive calls return true (meaning the word was found along that path), return true.
7
Step 7: Before returning, restore the original character of the current cell to the board.
8
Step 8: If the backtrack function returns false for all starting cells, it means the word was not found in the board, so return false.

💡

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(L)

📝

Why?

The time complexity comes from the nested loops iterating through each cell in the board (M * N) and the recursive calls exploring up to 4 directions for each character of the word (4^L). The space complexity arises from the recursion stack, which can grow up to the length of the word L in the worst case.

📖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

Iterative Depth-First Search (DFS) with Stack

Instead of using recursion, an iterative DFS can be implemented using a stack to keep track of the cells to visit. This approach avoids the function call overhead and potential stack overflow issues with very long words or large boards.

Time: O(M * N * 4^L)Space: O(L)

Trade-offs: Iterative DFS can be slightly more complex to implement, but avoids the overhead of recursive calls. It might be preferable for very large grids or long words where stack overflow is a concern.

✨

Key Insights

1Insight 1: Backtracking is suitable because we need to explore all possible paths from each cell in the grid to see if any path matches the given word. If a path doesn't work, we need to backtrack and try a different path.
2Insight 2: A key optimization is to temporarily mark visited cells during the backtracking search to avoid cycles and using the same cell multiple times.
3Insight 3: The search process needs to start from every cell in the grid because the word can potentially start at any location.

📚

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. The code implicitly handles the empty board case since the loop won't execute. An empty word would immediately return true from the backtrack function because the index would equal the word length.
Edge case 2: Word longer than the number of cells in the board. The algorithm will explore paths up to the length of the word. If the path leads outside the board boundaries, or a wrong character is encountered, that branch of search is discarded, eventually leading to the word not found.
Edge case 3: The same letter cell may not be used more than once. This is enforced by temporarily marking the current cell as visited ('#') during the recursion, preventing it from being reused in the same path.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not restoring the original character of the board after the backtrack function returns. This can lead to incorrect results because other paths might be blocked by the modified board.

✗Common mistake 2: Not handling the boundary conditions correctly, leading to out-of-bounds errors when accessing the board. The code correctly checks for `r < 0 || r >= rows || c < 0 || c >= cols` before accessing `board[r][c]`.

✗Common mistake 3: Forgetting to check if the current cell's character matches the current character in the word. The code ensures this with `board[r][c] != word[index]`.

✅

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: Text search in a grid or matrix, like finding patterns in DNA sequences or identifying specific phrases in a document.

🏦Real-world scenario 2: Pathfinding algorithms in games, where the board represents the game world and the word represents a sequence of movements needed to reach a destination.

💡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

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ 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: August 19, 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

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Word Search"?

For this medium-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?