wayetan
3/2/2014 - 12:49 AM

## Word Search

Word Search

``````/**
* Given a 2D board and a word, find if the word exists in the grid.
* The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring.
* The same letter cell may not be used more than once.
* For example,
* Given board =
* [
["ABCE"],
["SFCS"],
]
* word = "ABCCED", -> returns true,
* word = "SEE", -> returns true,
* word = "ABCB", -> returns false.
*/
public class Solution {
public boolean exist(char[][] board, String word) {
if(board == null)
return false;
if(word == null || word.length() == 0)
return true;
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(DFS(board, i, j, word, 0, visited))
return true;
}
}
return false;
}
private boolean DFS(char[][] board, int i, int j, String word, int len, boolean[][] visited) {
if(visited[i][j] || board[i][j] != word.charAt(len))
return false;
if(len == word.length() - 1)
return true;
visited[i][j] = true;
// walk left;
if(i != 0 && DFS(board, i - 1, j, word, len + 1, visited))
return true;
// walk right;
if(i != board.length - 1 && DFS(board, i + 1, j, word, len + 1, visited))
return true;
// walk up
if(j != 0 && DFS(board, i, j - 1, word, len + 1, visited))
return true;
// walk down
if(j != board[0].length - 1 && DFS(board, i, j + 1, word, len + 1, visited))
return true;
// backtracking
visited[i][j] = false;
return false;
}
}
``````