79. Word Search

Posted on | In
Words count in article: 524 | Reading time ≈ 2

题目

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.

示例1:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

提示:

  • board and word consists only of lowercase and uppercase English letters.
  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • 1 <= word.length <= 10^3

解法

解法一：

深度优先遍历

分解为以下步骤：

  1. 遍历board中的每个字符，找到搜索起始点-即和word字符串第一个相等的char
  2. 对每个起始点，进行dfs搜索
  3. 如果搜索的时候，发现index已经等于word的长度了，则表示已经找到匹配的字符串了，直接返回
  4. 如果列或者行越界了，小于0或者大于列长度或者大于行长度，又或者当前的字符串和word对应位置的字符串不一致，说明当前路径是不可行的，直接返回
  5. 把当前节点置为一个特殊字符，表示已经使用，不可再用第二次，继续从当前节点的上下左右位置开始搜索
  6. 把当前节点置为原字符，供下次搜索使用

JAVA

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
public boolean exist(char[][] board, String word) {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == word.charAt(0)) {
					if (dfs(i, j, 0, board, word)) {
						return true;
					}
				}
			}
		}

		return false;
	}

	private boolean dfs(int row, int col, int index, char[][] board, String word) {
		if (index == word.length()) {
			// 当前所有的字符已经匹配上
			return true;
		}

		if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
				|| board[row][col] != word.charAt(index)) {
			return false;
		}
		char c = board[row][col];
		board[row][col] = '#';
		boolean result = dfs(row + 1, col, index + 1, board, word) || dfs(row - 1, col, index + 1, board, word)
				|| dfs(row, col + 1, index + 1, board, word) || dfs(row, col - 1, index + 1, board, word);
		board[row][col] = c;
		return result;
	}
0%