79. 单词搜索

079.单词搜索

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上

（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格

中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平

相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

难度

中等

示例

示例 1：

079.%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2-20230921135734.png

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =

"ABCCED"

输出：true

示例 2：

079.%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2-20230921135755.png

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

输出：true

示例 3：

079.%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2-20230921135815.png

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

输出：false

分析 1

本题我们要用到的算法是——深度优先搜索+回溯算法。

首先，在 board 中找到 word 的第一个字符，然后再往其他方向查找有没有第二个字符，

但是这么做的话，第三步有可能回到原点（第二个字符折回到第一个字符），从而陷入无

限递归的死局。

所以我们要引入一个布尔型的二维数组 vis[][]，来标记哪些点已经走过的，走过的就不能

再次选择。

当四个方向都没有可行的策略时，我们就要用到——回溯算法，上一题中我们其实有聊

过。

回溯算法其实也好理解，毕竟一条路走到黑，走不出去的时候，最好换条路走。

来看题解。

class Solution {

// 定义四个方向，即上下左右

int[] dirX = {0, 0, 1, -1};

int[] dirY = {1, -1, 0, 0};

// 用于记录某个位置是否已经访问过

boolean[][] vis;

// 二维字符数组，即题目给定的 board

char[][] map;

// 要查找的单词

String str;

public boolean exist(char[][] board, String word) {

vis = new boolean[board.length][board[0].length];

map = board;

str = word;

// 遍历整个 board，查找起点

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))

return true; // 如果找到了单词，则返回 true

}

}

}

// 所有位置都尝试过但没找到，返回 false

return false;

}

 // 判断移动是否合法

private boolean checkMove(int posX,int posY){

return posX < map.length && posX >= 0 && posY < map[0].length && posY

>= 0 && !vis[posX][posY];

}

// 深度优先搜索函数

private boolean DFS(int posX,int posY,int step){

// 当前位置字符与单词不匹配，返回 false

if(map[posX][posY] != str.charAt(step))

return false;

// 如果匹配到单词的最后一个字符，返回 true

if(step == str.length() - 1)

return true;

boolean res = false;

vis[posX][posY] = true; // 标记当前位置已访问

// 遍历四个方向

for(int i = 0;i < 4 && !res;i++){

int nextX = posX + dirX[i];

int nextY = posY + dirY[i];

// 如果移动合法并且下一个位置匹配，继续深度优先搜索

if(checkMove(nextX,nextY) && DFS(nextX,nextY,step + 1))

res = true;

}

// 回溯，即撤销当前位置的访问标记，以便后续的搜索

vis[posX][posY] = false;

return res;

}

}

这段代码在一个二维字符数组（即 board）中查找一个特定的单词 word 是否存在。搜索

的方式是从一个字符开始，然后向上下左右四个方向移动。这是一个典型的深度优先搜

索，并且涉及到回溯，即当当前路径不可能匹配整个单词时，需要退回到上一步并尝试其

他可能的路径。

简单的图解：

1. 假设 board 是这样的：

ABC

DEF

GHI

2. 要查找的单词是：“BEHI”。

3. 搜索流程：

从“B”开始（即第一行第二列），然后向四个方向搜索：

A [B] C --> A [B] [C]

D E F D E F

G H I G H I

从“C”开始，无法匹配“BEHI”，所以回退到“B”，然后尝试其他方向。

A [B] C --> A [B] C

D [E] F D [E] F

G H I G H I

从“E”开始，接下来的字母是“H”，所以向下搜索。

A [B] C --> A [B] C

D [E] F D [E] F

G [H] I G [H] I

接下来的字母是“I”，所以再次向下搜索。

A [B] C --> A [B] C

D [E] F D [E] F

G [H] [I] G [H] [I]

这样，就找到了整个单词“BEHI”。

079.%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2-20230921141736.png

分析 2

LeetCode 的原题中有提示我们使用剪枝，我们来试一下，效率会不会更高。

剪枝算法是在搜索算法中用于减少无用或冗余搜索路径的策略。通过排除某些选择，可以

提高搜索效率。

将前面的回溯策略加上剪枝优化的思路如下：

1. 早停策略：如果当前已经匹配的字符数量与目标单词的长度相同，则可以提前终止搜

索，因为我们已经找到一个匹配的路径。

2. 字符不匹配：如果 board[x][y]与目标单词中的当前字符不匹配，则立即返回 false，

无需进一步搜索。

3. 避免重复访问：为了防止在搜索过程中重复访问同一个格子，我们可以用一个标记数

组 visited 来记录哪些格子已经被访问过。当我们从一个格子返回时，需要将其标记

为未访问。

下面是带有剪枝策略的题解：

class Solution {

private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

private int m, n;

public boolean exist(char[][] board, String word) {

m = board.length;

n = board[0].length;

boolean[][] visited = new boolean[m][n];

// 遍历每一个起始点，尝试从这个点开始搜索

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (dfs(board, word, 0, i, j, visited)) {

return true;

}

}

}

return false;

}

private boolean dfs(char[][] board, String word, int index, int x, int y, boolean[]

[] visited) {

// 剪枝：当前位置的字符与目标字符不匹配

if (board[x][y] != word.charAt(index)) {

return false;

}

// 所有字符都已匹配，返回 true

if (index == word.length() - 1) {

return true;

}

visited[x][y] = true;

boolean result = false;

for (int[] direction : directions) {

int newX = x + direction[0], newY = y + direction[1];

if (newX >= 0 && newX < m && newY >= 0 && newY < n && !

visited[newX][newY]) {

if (dfs(board, word, index + 1, newX, newY, visited)) {

result = true;

break; // 剪枝：一旦有一个方向匹配成功，就中止其他方向的搜索

}

 }

}

visited[x][y] = false;

return result;

}

}

以上代码中，我们使用了 visited 数组来标记已经访问过的单元格。我们还使用了一种早

停策略：当在一个方向上的搜索匹配成功时，我们就中止其他方向的搜索。

通过执行结果可以看得出来，剪枝后的效率有所提升。

079.%E5%8D%95%E8%AF%8D%E6%90%9C%E7%B4%A2-20230921151427.png

ACM 模式

为了方便大家理解，我这里把代码加完整，直接以 ACM 的模式（带输入输出）来看一

下。

package com.github.paicoding.forum.test.leetcode;

/**

*

* @author 沉默王二

* @date 9/21/23

*/

import java.util.Scanner;

public class WordSearch {

private static final int[] dirX = {0, 0, 1, -1};

private static final int[] dirY = {1, -1, 0, 0};

private static boolean[][] vis;

private static char[][] map;

private static String str;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

// 输入提示语句

 System.out.println("请输入二维数组的行数：");

int rows = scanner.nextInt();

System.out.println("请输入二维数组的列数：");

int cols = scanner.nextInt();

map = new char[rows][cols];

System.out.println("请输入二维数组：");

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {

map[i][j] = scanner.next().charAt(0);

}

}

System.out.println("请输入要查找的字符串：");

str = scanner.next();

System.out.println(exist(map, str));

}

public static boolean exist(char[][] board, String word) {

vis = new boolean[board.length][board[0].length];

map = board;

str = 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)) {

return true;

}

}

}

}

return false;

}

private static boolean checkMove(int posX, int posY) {

return posX < map.length && posX >= 0 && posY < map[0].length && posY

>= 0 && !vis[posX][posY];

}

private static boolean DFS(int posX, int posY, int step) {

if (map[posX][posY] != str.charAt(step)) return false;

if (step == str.length() - 1) return true;

vis[posX][posY] = true;

for (int i = 0; i < 4; i++) {

int nextX = posX + dirX[i];

int nextY = posY + dirY[i];

if (checkMove(nextX, nextY) && DFS(nextX, nextY, step + 1)) {

return true;

}

 }

vis[posX][posY] = false;

return false;

}

}

输入示例如下所示：

请输入二维数组的行数：

3

请输入二维数组的列数：

4

请输入二维数组：

ABCE

SFCS

ADEE

请输入要查找的字符串：

ABCCEDF

true

总结

这类递归回溯的算法，最需要注意的地方就是，在回溯的时候，必须要还原“事故现场”，

让一切都回到原点，接下来才能做出更好的选择。

力扣链接：https://leetcode.cn/problems/word-search/

更新: 2023-09-21 07:31:26

原文: https://www.yuque.com/itwanger/czfoq9/eebn8r