Word Search

class Solution {
public:
    bool exist(vector<vector<char>>& b, string word) {
        int m = b.size(), n = b[0].size();
        function<bool(int,int,int)> dfs = [&](int r, int c, int i) -> bool {
            if (i == (int)word.size()) return true;
            if (r < 0 || r >= m || c < 0 || c >= n || b[r][c] != word[i]) return false;
            char saved = b[r][c];
            b[r][c] = '#';
            bool found = dfs(r+1,c,i+1) || dfs(r-1,c,i+1) || dfs(r,c+1,i+1) || dfs(r,c-1,i+1);
            b[r][c] = saved;
            return found;
        };
        for (int r = 0; r < m; ++r)
            for (int c = 0; c < n; ++c)
                if (dfs(r, c, 0)) return true;
        return false;
    }
};

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var dfs func(r, c, i int) bool
    dfs = func(r, c, i int) bool {
        if i == len(word) {
            return true
        }
        if r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[i] {
            return false
        }
        saved := board[r][c]
        board[r][c] = '#'
        found := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) || dfs(r, c+1, i+1) || dfs(r, c-1, i+1)
        board[r][c] = saved
        return found
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if dfs(r, c, 0) {
                return true
            }
        }
    }
    return false
}

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(r: int, c: int, i: int) -> bool:
            if i == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i]:
                return False
            saved = board[r][c]
            board[r][c] = '#'
            found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                     or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
            board[r][c] = saved
            return found

        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        return False

function exist(board, word) {
    const m = board.length, n = board[0].length;
    const dfs = (r, c, i) => {
        if (i === word.length) return true;
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
        const saved = board[r][c];
        board[r][c] = '#';
        const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
            || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = saved;
        return found;
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

class Solution {
    private char[][] board;
    private String word;
    private int m, n;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        m = board.length;
        n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int r, int c, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(i)) return false;
        char saved = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
            || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = saved;
        return found;
    }
}

function exist(board: string[][], word: string): boolean {
    const m = board.length, n = board[0].length;
    const dfs = (r: number, c: number, i: number): boolean => {
        if (i === word.length) return true;
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false;
        const saved = board[r][c];
        board[r][c] = '#';
        const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
            || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = saved;
        return found;
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}