79-单词搜索

阅读数：46次 2019-08-13

79. 单词搜索

题目描述：

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

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

示例:

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

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

解题思路：

由于是路径判断的题目类型，需要顺序推进，那么肯定是要深度遍历DFS的做法了。

在设计的时候，我们知道已经遍历了的坐标需要标记，进行剪枝操作。并且同一单元格内的字母不允许重复使用。然而如果这个支路遍历了发现这个字母不相等，但之前的字母可能在另外一条支路的遍历延伸中又转回来了。

例如：在该 3 * 4 的数组中寻找一个字符串 ABCESEEEFS

这就需要用到回溯思想了，如果一条节点临近的多个节点都可以访问，也就是分支时，判断后续是否可以完全跑通，跑不通我们应该将hasVisit数组的堵塞的支路的坐标对其复原。

解题代码：

public class WordSearch79 {

	public boolean exist(char[][] board, String word) {
		if (word == null || board == null || word.length() < 1 || board.length < 1)
			return false;

		int xlen = board[0].length;
		int ylen = board.length;
		// 一个二维数组，用一个数组进行记录
		// 将首字母在board中出现的坐标进行记录
		char firstChar = word.charAt(0);
		for (int i = 0; i < ylen; i++) {
			for (int j = 0; j < xlen; j++) {
				if (board[i][j] == firstChar) {
					boolean[][] hasVisit = new boolean[ylen][xlen];
					if (backtrack(i, j, board, hasVisit, word, 0))
						return true;
				}
			}
		}

		return false;
	}

	private boolean backtrack(int x, int y, char[][] board, boolean[][] hasVisit, String word, int i) {
		if (i == word.length())
			return true;

		if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != word.charAt(i)
				|| hasVisit[x][y])
			return false;

		// 如何解决当分叉遍历后，一条遍历多个节点后需要回到其中的另一个子节点，而这个子节点已经当做遍历过的这种情况
		hasVisit[x][y] = true;

		// 判断后续该路径是否可以走通，如果不可以还原 hasVisit,不要影响其他分支的遍历
		boolean flag = backtrack(x + 1, y, board, hasVisit, word, i + 1)
				|| backtrack(x - 1, y, board, hasVisit, word, i + 1)
				|| backtrack(x, y + 1, board, hasVisit, word, i + 1)
				|| backtrack(x, y - 1, board, hasVisit, word, i + 1);

		if (!flag)
			hasVisit[x][y] = false;

		return flag;
	}

	public static void main(String[] args) {
		char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'E', 'S' }, { 'A', 'D', 'E', 'E' } };
		String word = "SEEEE";
		WordSearch79 demo = new WordSearch79();
		System.out.println(demo.exist(board, word));
	}
}