79. Word Search

Задача

Дана сетка символов и слово. Верните true, если слово можно составить из соседних (по горизонтали/вертикали) ячеек, не используя ячейку дважды.

Примеры

Пример 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Пример 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Пример 3

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

Решение

Решение

/**
 * Time Complexity: O(N * M * 3^L)
 * Space Complexity: O(L)
 * N = rows, M = cols, L = word.length
 */
var exist = function(board, word) {
    const rows = board.length;
    const cols = board[0].length;
 
    function check(r, c, index) {
        if (index === word.length) return true;
 
        if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
            return false;
        }
 
        const temp = board[r][c];
        board[r][c] = '#'; // Mark as visited
 
        const found = check(r + 1, c, index + 1) ||
            check(r - 1, c, index + 1) ||
            check(r, c + 1, index + 1) ||
            check(r, c - 1, index + 1);
 
        board[r][c] = temp; // Backtrack
        return found;
    }
 
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (check(r, c, 0)) return true;
        }
    }
 
    return false;
};