LeetCode 79: Word Search - DFS Solution Explained (C++, Java, Python, C#)

Solve LeetCode’s Word Search problem efficiently using Depth-First Search (DFS) with backtracking. This comprehensive guide provides optimized code implementations in four languages, complexity analysis, and a step-by-step breakdown of the algorithm. Perfect for coding interview preparation!

Problem Description

Given an m x n grid of characters (board) and a string (word), determine if the word exists in the grid. The word must be constructed from adjacent cells (horizontal or vertical neighbors), with each cell used only once.

Example:

For board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] and word = "ABCCED", the answer is true.

Solution Approach

Depth-First Search (DFS) with Backtracking

Grid Traversal: Start from each cell matching the first character of the word.
DFS Exploration: Check all 4-directional neighbors recursively.
Visited Tracking: Mark cells as visited during exploration and unmark during backtrack.
Termination: Return success when reaching the word’s end.

Key Optimization:

Avoid string slicing by using a character index.
Immediate return when any path succeeds.

Solution Code

Java Implementation:

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length 
            || board[i][j] != word.charAt(index)) return false;
        
        char temp = board[i][j];
        board[i][j] = '#';  // Mark visited
        
        boolean found = dfs(board, word, i+1, j, index+1)
                     || dfs(board, word, i-1, j, index+1)
                     || dfs(board, word, i, j+1, index+1)
                     || dfs(board, word, i, j-1, index+1);
        
        board[i][j] = temp;  // Backtrack
        return found;
    }
}

Python Implementation:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, index):
            if index == len(word):
                return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) \
               or board[i][j] != word[index]:
                return False
            temp, board[i][j] = board[i][j], '#'
            found = dfs(i+1, j, index+1) or dfs(i-1, j, index+1) \
                    or dfs(i, j+1, index+1) or dfs(i, j-1, index+1)
            board[i][j] = temp
            return found
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

C++ Implementation:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); ++i)
            for(int j = 0; j < board[0].size(); ++j)
                if(dfs(board, word, i, j, 0))
                    return true;
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
        if(index == word.size()) return true;
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() 
            || board[i][j] != word[index]) return false;
        
        char temp = board[i][j];
        board[i][j] = '#';
        
        bool found = dfs(board, word, i+1, j, index+1)
                  || dfs(board, word, i-1, j, index+1)
                  || dfs(board, word, i, j+1, index+1)
                  || dfs(board, word, i, j-1, index+1);
        
        board[i][j] = temp;
        return found;
    }
};

C# Implementation:

public class Solution {
    public bool Exist(char[][] board, string word) {
        for(int i = 0; i < board.Length; i++) {
            for(int j = 0; j < board[0].Length; j++) {
                if(Dfs(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    private bool Dfs(char[][] board, string word, int i, int j, int index) {
        if(index == word.Length) return true;
        if(i < 0 || i >= board.Length || j < 0 || j >= board[0].Length 
            || board[i][j] != word[index]) return false;
        
        char temp = board[i][j];
        board[i][j] = '#';
        
        bool found = Dfs(board, word, i+1, j, index+1)
                  || Dfs(board, word, i-1, j, index+1)
                  || Dfs(board, word, i, j+1, index+1)
                  || Dfs(board, word, i, j-1, index+1);
        
        board[i][j] = temp;
        return found;
    }
}

Complexity Analysis

Time Complexity: O(N × M × 4^L), where N is the number of rows, M is the number of columns, and L is the length of the word. This accounts for exploring up to four directions from each cell.

Common Pitfalls to Avoid:

Forgetting to backtrack visited marks
Index mismatches between word and grid positions
Not handling empty input edge cases

This optimized approach ensures efficient exploration of all potential word paths while maintaining clean code structure. The backtracking mechanism keeps space complexity minimal compared to using a separate visited matrix[1][2][4].

Citations:
LeetCode 79. Word Search – Dylan’s Blog Word Search Solution on GitHub Word Search Video Tutorial (Python) Test Case Debugging Discussion Java Solution Walkthrough Edge Case Analysis Optimization Techniques Video Bilingual Solution Explanation DFS Strategy Breakdown Time Complexity Deep Dive Visited Tracking Discussion Alternative Implementations Recursion Visualization Guide Interview Preparation Tips Backtracking Masterclass

❓ Frequently Asked Questions (FAQ)

Q1. What is the main algorithm used to solve the Word Search problem?
A: The solution uses Depth-First Search (DFS) with backtracking to explore potential paths in the grid that match the target word.

Q2. Why do we use backtracking in this problem?
A: Backtracking allows us to explore all possible paths to form the word and revert changes (i.e., unmark visited cells) when a path doesn’t lead to a valid solution.

Q3. How do we keep track of visited cells?
A: We temporarily mark the cell as visited by changing its value (e.g., to '#') during the DFS and restore it after backtracking.

Q4. Can a cell be used more than once in the same word path?
A: No, each cell must be used only once in a single path to form the word. That’s why visited tracking is important.

Q5. What are the time and space complexities of this solution?
A:

Time Complexity: O(N × M × 3^L) where N = rows, M = cols, and L = length of the word
Space Complexity: O(L) due to the recursion stack in DFS

Q6. Is it necessary to check all cells as starting points?
A: Yes, since the word can begin from any cell, we must iterate over the entire grid and trigger DFS from matching starting characters.

Q7. What happens if the grid is empty or the word is empty?
A: These are edge cases. The function should return false if the grid is empty, and true only if the word is also empty.

Q8. Why not use a separate visited matrix?
A: For optimization, we mark visited cells in-place to reduce space usage, eliminating the need for an extra matrix.

Q9. What languages is the solution implemented in?
A: The post includes working code in Java, Python, C++, and C#.

Q10. How is this useful for coding interviews?
A: Word Search tests key concepts like DFS, recursion, backtracking, and grid traversal, making it a popular problem in technical interviews.

LeetCode 79: Word Search – DFS Solution Explained (C++, Java, Python, C#)