79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 public class Solution {
 2     private boolean[][] flag = null;
 3     private char[] words = null;
 4     private int row = 0;
 5     private int col = 0;
 6 
 7     // i,j是word[0]的位置; cur表示words中的位置
 8     private boolean helper(char[][] board, int cur, int i, int j) {
 9         if (cur == words.length)
10             return true;
11         // 上
12         if (i-1 >= 0 && !flag[i-1][j] && board[i-1][j] == words[cur]) {
13             flag[i-1][j] = true;
14             if (helper(board, cur+1, i-1,j))
15                 return true;
16             flag[i-1][j] = false;
17         }
18         // 下
19         if (i+1 < row && !flag[i+1][j] && board[i+1][j] == words[cur]) {
20             flag[i+1][j] = true;
21             if (helper(board, cur+1, i+1, j))
22                 return true;
23             flag[i+1][j] = false;
24         }
25         // 左
26         if (j-1 >= 0 && !flag[i][j-1] && board[i][j-1] == words[cur]) {
27             flag[i][j-1] = true;
28             if (helper(board, cur+1, i, j-1))
29                 return true;
30             flag[i][j-1] = false;
31         }
32         // 右
33         if (j+1 < col && !flag[i][j+1] && board[i][j+1] == words[cur]) {
34             flag[i][j+1] = true;
35             if (helper(board, cur+1, i, j+1))
36                 return true;
37             flag[i][j+1] = false;
38         }
39         return false;
40     }
41 
42     public boolean exist(char[][] board, String word) {
43         words = word.toCharArray();
44         flag = new boolean[board.length][board[0].length];
45         row = board.length;
46         col = board[0].length;
47         for (int i = 0; i < row; i++) {
48             for (int j = 0; j < col; j++) {
49                 if (board[i][j] == words[0]) {
50                     flag[i][j] = true;
51                     if (helper(board, 1, i, j))
52                         return true;
53                     flag[i][j] = false;
54                 }
55             }
56         }
57         return false;
58     }
59 
60     public static void main(String[] args) {
61         char[][] board = {
62                 {'A','B','C','E'},
63                 {'S','F','C','S'},
64                 {'A','D','E','E'}
65         };
66         boolean abcced = new Solution().exist(board, "SEE");
67         System.out.println("abcced = " + abcced);
68     }
69 }