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"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution: treat each cell as a node of a graph, and its four cells (up, down, left, right) as neighbors. Use DFS, and use a visited array to mark if a node has been already visited. Starting a DFS from every cell of the board. If find, return true.

Java语言: WordSearch

01 public boolean exist(char[][] board, String word) {
02     int numRows=board.length;
03     int numCols=board[0].length;      
04     boolean [][]visited=new boolean[numRows][numCols];
05     for(int i=0;i<numRows;i++)
06     {
07         for(int j=0;j<numCols;j++)
08         {
09             //DFS starting from each cell
10             if(exist(board, i, j, 0, visited, word))
11                 return true;
12             //reset visited    
13             visited=new boolean[numRows][numCols];
14         }
15     }
16     return false;
17 }
18 
19 //DFS for substring starting at position i of word
20 public boolean exist(char[][] board, int row, int col, int i, boolean[][]visited, String word)
21 {
22     if(i==word.length())
23     {
24         return true;
25     }
26     if(row<0||row>=board.length||col<0 || col>=board[0].length)
27     {
28         return false;
29     }
30     if(!visited[row][col])
31     {
32         //set the current position of board as visited
33         if(board[row][col]==word.charAt(i))
34         {
35             visited[row][col]=true;
36             //DFS on its four neighbor
37             boolean case1=exist(board, row+1, col, i+1, visited, word);
38             boolean case2=exist(board, row-1, col, i+1, visited, word);
39             boolean case3=exist(board, row, col+1, i+1, visited, word);
40             boolean case4=exist(board, row, col-1, i+1, visited, word);              
41             return case1||case2||case3||case4;              
42         }          
43     }
44     return false;
45 }