Thinking process

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    public boolean exist(char[][] board, String word) {
        // write your code here
        //validate input
        if (board == null || board.length == 0) return false;
        if (board[0].length == 0) return false;

        int n = board.length;
        int m = board[0].length;

        if (word.length() == 0) return true;
        char[] chars = word.toCharArray();


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                boolean[][] visited = new boolean[n][m];
                if (backtrack(chars, board, visited, 0, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean backtrack(char[] chars, char[][] board, boolean[][] visited, int index, int x, int y)
    {
        if (index == chars.length) {
            return true;
        }

        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;

        if (chars[index] != board[x][y] || visited[x][y]) return false;



        visited[x][y] = true;
        //up
        if(backtrack(chars, board, visited, index + 1, x - 1, y)) return true;

        //down
        if(backtrack(chars, board, visited, index + 1, x + 1, y)) return true;

        //left
        if(backtrack(chars, board, visited, index + 1, x, y - 1)) return true;

        //right
        if(backtrack(chars, board, visited, index + 1, x, y + 1)) return true;

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