algoadvance

Leetcode 79. Word Search

Problem Statement

Given an m x n board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are those 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"
Output: true

Example 3:
Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCB"
Output: false

Clarifying Questions

1. What kind of characters does the board contain?
   • The board contains only uppercase and lowercase English letters.
2. What is the maximum size of the board?
   • The maximum size isn’t given, but we can assume typical board sizes like 100x100.
3. Any constraints on the word length?
   • The word length can be from 1 to the number of cells in the board.

Strategy

• Backtracking Approach:
  1. Iterate over every cell in the board and use a recursive (DFS) backtracking approach to check if the word can be found starting from that cell.
  2. Mark cells as visited by temporarily changing their value.
  3. Explore all four potential directions (up, down, left, right) around each cell.
  4. If any cell sequence forms the word, return true.
  5. If the entire board is explored without forming the word, return false.

Time Complexity

• The time complexity is O(m * n * 4^L), where m is the number of rows, n is the number of columns, and L is the length of the word. This is because each cell can be visited and each visit recursively explores up to four directions.

Code

#include <vector>
#include <string>

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

private:
    bool dfs(std::vector<std::vector<char>>& board, const std::string& word, int index, int x, int y) {
        if (index == word.size()) return true;
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) return false;
        if (board[x][y] != word[index]) return false;

        char temp = board[x][y];
        board[x][y] = '#'; // Mark as visited

        bool found = dfs(board, word, index + 1, x + 1, y) ||
                     dfs(board, word, index + 1, x - 1, y) ||
                     dfs(board, word, index + 1, x, y + 1) ||
                     dfs(board, word, index + 1, x, y - 1);

        board[x][y] = temp; // Restore original value
        return found;
    }
};

This implementation uses a helper function dfs for depth-first search to explore all possible paths to construct the word from the given board, marking visited cells temporarily and restoring them after the exploration.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?