#79. 单词搜索

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

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

示例:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

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

提示：

board和word中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package xyz.onns.leetcode;

/**
 * @Author Onns
 * @Date 2020/9/13 2:57 PM
 * @Version 1.0
 * @Website https://onns.xyz/blog/
 */
public class WordSearch {
	public static void main(String[] args) {
		new WordSearch().new Solution().test();
	}

	class Solution {
		public boolean exist(char[][] board, String word) {
			int n = board.length;
			int m = board[0].length;
			boolean[][] use = new boolean[n][m];
			char first = word.charAt(0);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (board[i][j] == first) {
						use[i][j] = true;
						if (dfs(board, word.toCharArray(), use, 1, n, m, i, j)) {
							use[i][j] = false;
							return true;
						}
						use[i][j] = false;
					}
				}
			}
			return false;
		}

		boolean dfs(char[][] board, char[] word, boolean[][] use, int index, int n, int m, int a, int b) {
			if (index == word.length) return true;

			int[] opx = {-1, 0, 0, 1};
			int[] opy = {0, -1, 1, 0};

			for (int i = 0; i < opx.length; i++) {
				int x = a + opx[i];
				int y = b + opy[i];
				if (legal(x, y, n, m) && board[x][y] == word[index] && !use[x][y]) {
					use[x][y] = true;
					if (dfs(board, word, use, index + 1, n, m, x, y)) {
						use[x][y] = false;
						return true;
					}
					use[x][y] = false;
				}
			}
			return false;
		}

		boolean legal(int i, int j, int n, int m) {
			return i >= 0 && i < n && j >= 0 && j < m;
		}

		void test() {
			System.out.println(exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED"));
			System.out.println(exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "SEE"));
			System.out.println(exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCB"));
			System.out.println(exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCESEEEFS"));
		}
	}
}