Question

How to search for a word in a grid of characters with C++

Answer 1

#include <functional>
#include <iostream>
#include <vector>

using std::vector;

bool wordExist(vector<vector<char>>& board, std::string word) {
    int rows = board.size();
    int cols = board[0].size();
        // i, j: Current cell coordinates.
        // k: Index of the current character in word.
        // Defining a lambda function. This allows the lambda to be recursive.
        
        // The & in [&] means the lambda captures all local variables by reference
        // to access and modify variables like board, rows, cols, and word
        std::function<bool(int, int, int)> backtrack = [&](int i, int j, int k) {
            // We've matched every character
            if (k == word.length()) {
                return true;
            }
            if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != word[k]) {
                return false;
            }

            char temp = board[i][j];
            // Temporarily mark the current cell as visited to avoid revisiting.
            board[i][j] = '\0';
            
            // Explore 4 directions (no diagonals): up, down, left, right.
            if (backtrack(i + 1, j, k + 1) || backtrack(i - 1, j, k + 1) || 
                backtrack(i, j + 1, k + 1) || backtrack(i, j - 1, k + 1)) {
                return true;
            }
            
            board[i][j] = temp; 
            return false;
        };
    
    // For each position (i, j): The program tries to start the word search from that cell.
    // i, j: coordinates of the current cell.
    // 0: the index of the first character in the word.
    
    // If backtrack returns true, it means the word was successfully 
    // found starting from that cell.
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (backtrack(i, j, 0)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    vector<vector<char>> grid = {{'a', 'b', 'c', 'e'},
                                 {'s', 'f', 'c', 's'},
                                 {'a', 'd', 'e', 'e'}};
    std::string word = "see";
    
    bool result = wordExist(grid, word);
    
    std::cout << result;
}



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <string>

// use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched. 

using std::vector;

// DFS helper
bool dfs(vector<vector<char>>& grid, int r, int c, const std::string& word, int index) {
    if (index == word.size())
        return true;

    int rows = grid.size();
    int cols = grid[0].size();

    if (r < 0 || c < 0 || r >= rows || c >= cols)
        return false;

    if (grid[r][c] != word[index])
        return false;

    char temp = grid[r][c];
    grid[r][c] = '#'; // mark visited

    bool found =
        dfs(grid, r + 1, c, word, index + 1) ||
        dfs(grid, r - 1, c, word, index + 1) ||
        dfs(grid, r, c + 1, word, index + 1) ||
        dfs(grid, r, c - 1, word, index + 1);

    grid[r][c] = temp; // restore
    
    return found;
}

// Main search function
bool wordExist(vector<vector<char>>& grid, const std::string& word) {
    int rows = grid.size();
    int cols = grid[0].size();

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

int main() {
    vector<vector<char>> grid = {
        {'a', 'b', 'c', 'e'},
        {'s', 'f', 'c', 's'},
        {'a', 'd', 'e', 'e'}
    };

    std::string word = "see";

    bool result = wordExist(grid, word);

    std::cout << result;  // prints 1 if found, 0 if not
}



/*
run:
 
1
 
*/


 

 

70+ SQL courses for beginners and professionals