DevExCode

LeetCode 79: Word Search Solution

Master LeetCode problem 79 (Word Search), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can perform a depth-first search (DFS) starting from each cell in the grid. At each step, we check if the current cell matches the next character in the word. If it does, we mark the cell as visited and recursively explore its neighboring cells. We continue this process until we either find the entire word or reach a dead end.

Algorithm:

  1. Iterate over each cell in the grid.
  2. For each cell, perform a DFS starting from that cell to check if the word can be formed.
  3. In the DFS function:
    • Check if the current cell is out of bounds or has already been visited.
    • Check if the current cell matches the next character in the word.
    • Mark the cell as visited, and recursively explore its neighboring cells.
  4. If the word is found during the DFS, return true. Otherwise, return false.

Time Complexity:

The time complexity of this approach is O(m * n * 4^l), where m and n are the dimensions of the grid, and l is the length of the word. The factor of 4^l comes from the branching factor of the DFS.

Space Complexity:

The space complexity is O(l), where l is the length of the word, due to the recursive calls in the DFS.

Solution Code

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, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, int i, int j, String word, 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] = ' ';
        boolean found = dfs(board, i + 1, j, word, index + 1)
                    || dfs(board, i - 1, j, word, index + 1)
                    || dfs(board, i, j + 1, word, index + 1)
                    || dfs(board, i, j - 1, word, index + 1);
        board[i][j] = temp;
        
        return found;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 79 (Word Search)?

This page provides optimized solutions for LeetCode problem 79 (Word Search) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 79 (Word Search)?

The time complexity for LeetCode 79 (Word Search) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 79 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 79 in Java, C++, or Python.

Back to LeetCode Solutions