79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

img

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

注意：

  • 主函数里面对每个元素进行回溯
  • 选择当前元素之后将其标记为已选择，已避免重复选择

Solution：

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
class Solution {
    public boolean exist(char[][] board, String word) {
        // 将字符串转换为字符数组
        char[] words = word.toCharArray();
        // 遍历二维数组的每一个元素
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                // 如果从当前位置开始的深度优先搜索找到单词，返回 true
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        // 如果遍历完所有位置都没有找到单词，返回 false
        return false;
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 检查边界条件以及当前字符是否匹配
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        // 如果已经匹配到单词的最后一个字符，返回 true
        if (k == word.length - 1) return true;
        
        // 临时保存当前字符，并标记为已访问
        char temp = board[i][j];
        board[i][j] = '\0';

        // 递归搜索上下左右四个方向
        boolean res = dfs(board, word, i + 1, j, k + 1) || 
                      dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || 
                      dfs(board, word, i, j - 1, k + 1);

        // 恢复当前字符，取消标记
        board[i][j] = temp;
        
        // 返回搜索结果
        return res;
    }
}