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;
}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment