Leetcode #79 Word Search

[yokostan]

class Solution {
    static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                    return true;
                }
            }
        }

        return false;
    }

    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }

        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }

        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) || 
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) || 
           search(board, word, i, j+1, index+1)){
            return true;
        }

        visited[i][j] = false;
        return false;
    }
}

Well, I did this after #124 , so I added many abundant things like position variable, index and count at first, until I saw this amazing solution. The backtracking part I did fine, but still not half as good as this solution I copied from others.

1. It is wise to use boolean visited instead of count < total in this problem, for we can wisely check and filter out the forbidden (visited element) routes and save us a lot of time.
2. It is even wiser to put each starting point in the main function and start from there to go to the helper backtracking function.
3. It is the wisest to rule out the edge cases and word.charAt(index) != board[i][j] and return false, so we can leave with the winners! And don't forget to set visited[i][j] back to false. Enjoy!