wordSearch79

class Solution {
    public boolean exist(char[][] board, String word) {
        return obhod (board, word);
    }
    static boolean obhod(char[][] matrix, String word) {
        boolean isFound = false;
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == word.charAt(0)) isFound = isGood(matrix, visited, word, i, j, 0) ;
                if(isFound) return isFound;
            }
        }
        return false;
    }

    static boolean isGood(char[][] matrix, boolean[][] visited, String word, int row, int col, int letter) {
        if ( row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length ) return  false;
        if(matrix[row][col] != word.charAt(letter) || visited[row][col] ) return false;
        if(matrix[row][col] == word.charAt(letter) && letter == word.length() - 1) return true;
        visited[row][col] = true;
        if(isGood(matrix, visited, word, row, col + 1, letter + 1)) return true;
        if(isGood(matrix, visited, word,  row + 1, col, letter + 1)) return true;
        if(isGood(matrix, visited, word, row, col - 1, letter + 1)) return true;
        if(isGood(matrix, visited, word, row - 1, col, letter + 1)) return true;
        visited[row][col] = false;
        return false;
        }

}