Wednesday, March 27, 2013

[LeetCode] Word Search


Thought:
It is a DFS problem.

Code:
public class Solution {
    public static boolean flag;
    public boolean exist(char[][] board, String word) {
        flag = false;
        int row = board.length;
        int column = board[0].length;
        boolean[][] visited = new boolean[row][column];
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                helper(board, i, j, word, visited);
            }
        }
        
        return flag;        
    }
    public void helper(char[][] board, int row, int column, String word, boolean[][] visited) {
        if (flag) return;
        if (word.length() == 0) {
            flag = true;
            return;        
        }
        if (row >= board.length || column >= board[0].length || row < 0 || column < 0) return;
        if (visited[row][column] || board[row][column] != word.charAt(0)) return;
        visited[row][column] = true;
        helper(board, row - 1, column, word.substring(1), visited);
        helper(board, row, column - 1, word.substring(1), visited);
        helper(board, row + 1, column, word.substring(1), visited);
        helper(board, row, column + 1, word.substring(1), visited); 
        visited[row][column] = false;
    }
}

No comments:

Post a Comment