Word Search - LeetCode Daily Challenge

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are 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

Try here before watching the video.

Video Solution

Java Code

class Solution {

    int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private boolean isValid(int x, int y, int m, int n) {
        if(x < 0 || y < 0 || x >= m || y >= n) return false;
        return true;
    }

    private boolean dfs(char[][] board, int x, int y, int m, int n, String word, int index, boolean[][] visited) {

        if(index == word.length() || (index == word.length() - 1 && board[x][y] == word.charAt(index))) return true;

        if(word.charAt(index) != board[x][y]) return false;

        visited[x][y] = true;
        boolean ans = false;

        for(int[] dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if(isValid(newX, newY, m, n) && !visited[newX][newY]) {
                ans = ans || dfs(board, newX, newY, m, n, word, index + 1, visited);
            }
        }

        visited[x][y] = false;
        return ans;

    }
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;

        boolean ans = false;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                boolean[][] visited = new boolean[m][n];

                if(board[i][j] == word.charAt(0)) {
                    ans = ans || dfs(board, i, j, m, n, word, 0, visited);
                    if(ans) return ans;
                }
            }
        }

        return ans;
    }
}

Python Code

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

        def isValid(x, y, m, n):
            return 0 <= x < m and 0 <= y < n

        def dfs(x, y, index, visited):
            nonlocal ans
            if index == len(word) or (index == len(word) - 1 and board[x][y] == word[index]):
                ans = True
                return
            if word[index] != board[x][y]:
                return

            visited[x][y] = True

            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if isValid(nx, ny, m, n) and not visited[nx][ny]:
                    dfs(nx, ny, index + 1, visited)

            visited[x][y] = False

        for i in range(m):
            for j in range(n):
                visited = [[False] * n for _ in range(m)]
                if board[i][j] == word[0]:
                    dfs(i, j, 0, visited)
                    if ans:
                        return True

        return ans

Javascript Code

var exist = function(board, word) {
    const m = board.length;
    const n = board[0].length;
    let ans = false;

    function isValid(x, y, m, n) {
        return x >= 0 && y >= 0 && x < m && y < n;
    }

    function dfs(x, y, index, visited) {
        if (index === word.length || (index === word.length - 1 && board[x][y] === word[index])) {
            ans = true;
            return;
        }
        if (word[index] !== board[x][y]) return;

        visited[x][y] = true;

        const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            if (isValid(nx, ny, m, n) && !visited[nx][ny]) {
                dfs(nx, ny, index + 1, visited);
            }
        }

        visited[x][y] = false;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const visited = new Array(m).fill(false).map(() => new Array(n).fill(false));
            if (board[i][j] === word[0]) {
                dfs(i, j, 0, visited);
                if (ans) return true;
            }
        }
    }

    return ans;
};

Go Code

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    var ans bool

    var isValid func(x, y, m, n int) bool
    isValid = func(x, y, m, n int) bool {
        return x >= 0 && y >= 0 && x < m && y < n
    }

    var dfs func(x, y, index int, visited [][]bool)
    dfs = func(x, y, index int, visited [][]bool) {
        if index == len(word) || (index == len(word)-1 && board[x][y] == word[index]) {
            ans = true
            return
        }
        if word[index] != board[x][y] {
            return
        }

        visited[x][y] = true

        directions := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

        for _, dir := range directions {
            nx, ny := x+dir[0], y+dir[1]
            if isValid(nx, ny, m, n) && !visited[nx][ny] {
                dfs(nx, ny, index+1, visited)
            }
        }

        visited[x][y] = false
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            visited := make([][]bool, m)
            for k := range visited {
                visited[k] = make([]bool, n)
            }
            if board[i][j] == word[0] {
                dfs(i, j, 0, visited)
                if ans {
                    return true
                }
            }
        }
    }

    return ans
}