Question

How to search for a word in a grid of characters with Java

Answer 1

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

public class WordSearch {

    public static boolean dfs(char[][] grid, int r, int c, String word, int index, boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }

        int rows = grid.length;
        int cols = grid[0].length;

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

        if (visited[r][c]) {
            return false;
        }

        if (grid[r][c] != word.charAt(index)) {
            return false;
        }

        visited[r][c] = true;

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

        visited[r][c] = false;
        return found;
    }

    public static boolean wordExist(char[][] grid, String word) {
        int rows = grid.length;
        int cols = grid[0].length;

        boolean[][] visited = new boolean[rows][cols];

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

    public static void main(String[] args) {
        char[][] grid = {
                {'a', 'b', 'c', 'e'},
                {'s', 'f', 'c', 's'},
                {'a', 'd', 'e', 'e'}
        };

        String word = "see";

        boolean result = wordExist(grid, word);

        System.out.println(result ? 1 : 0);
    }
}



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals