Word Search 解答

Question

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

Because we have four choices to go, so this problem is not suitable to be solved by DP.

We use DFS here to traverse all possible paths.

One tricky note here is to check whether target equals to board[i][j] at every begining.

 1 public class Solution {
 2     public int[][] directions = {{0, 1},{0, -1},{1, 0},{-1, 0}};
 3     
 4     public boolean exist(char[][] board, String word) {
 5         int m = board.length, n = board[0].length;
 6         boolean[][] visited = new boolean[m][n];
 7         for (int i = 0; i < m; i++)
 8             Arrays.fill(visited[i], false);
 9         char target = word.charAt(0);
10         for (int i = 0; i < m; i++) {
11             for (int j = 0; j < n; j++) {
12                 if (dfsSearch(board, word, 0, visited, i, j))
13                     return true;
14             }
15         }
16         return false;
17     }
18     
19     private boolean dfsSearch(char[][] board, String word, int index, boolean[][] visited, int startX, int startY) {
20         if (index >= word.length())
21             return true;
22         int m = board.length, n = board[0].length;
23         if (startX < 0 || startX >= m || startY < 0 || startY >= n)
24             return false;
25         char target = word.charAt(index);
26         if (board[startX][startY] != target)
27             return false;
28         if (visited[startX][startY])
29             return false;
30         visited[startX][startY] = true;
31         
32         // Traverse four directions
33         boolean result = dfsSearch(board, word, index + 1, visited, startX, startY + 1) ||
34                         dfsSearch(board, word, index + 1, visited, startX, startY - 1) ||
35                         dfsSearch(board, word, index + 1, visited, startX + 1, startY) ||
36                         dfsSearch(board, word, index + 1, visited, startX - 1, startY);
37         // Reset visited[startX][startY]
38         visited[startX][startY] = false;
39         return result;
40     }
41 }