LeetCode高频题79. 单词搜索，如果 word 存在于网格中，返回 true ；否则，返回 false

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

---

文章目录

• LeetCode高频题79. 单词搜索，如果 word 存在于网格中，返回 true ；否则，返回 false
• • @[TOC](文章目录)
• 题目
• 一、审题
• 典型的业务限制类型暴力递归dfs遍历+剪枝策略
• f(board,i,j,word,k)怎们写？
• 本题解题主函数
• • LeetCode测试：  
• 我之前写的别的版本的代码，有点负责，当时不知道控制word从k--N位置去走，而是用path记录走过的单词是谁，对比word，这样过于复杂
• 总结

题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

一、审题

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出：false

不能往回走

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

---

典型的业务限制类型暴力递归dfs遍历+剪枝策略

dfs遍历
每一个ij为出发点，看看能走出word来吗，OK吗？？
有其一OK，就true
全部出发都不行？那不好意思
所以其实起点就要对上word那个字符的首字符

来到网格的ij位置，我们先看加入记录的路径path，判断OK与否？
OK的话，那就返回结果了
同时记录这个字符，表示不能再返回来访问了

没有OK的话，去上下左右四个方向试试——有一条路径OK，就算OK

正常往前走，不会退，是OK的，下面这个就是

走过的就不行

定义一个dfs函数：
f(board,i,j,word,k)
从board的ij出发，能否搞定word从k出发–N位置的所有单词？？？
word的k位置之前的所有位置搞定了

主函数就是调用：
f(board,i,j,word,0)，board整个表格，能走出word整体单词来吗？？？？

至于ij就是o（mn）遍历一遍，看看所有出发点，谁OK？？？

---

f(board,i,j,word,k)怎们写？

（0）如果k=N的话，word已经被搞定了，都走出来了，美滋滋，return true

因为f是：从board的ij出发，能否搞定word从k出发–N位置的所有单词？？？
word的k位置之前的所有位置搞定了：0–N-1搞定

（1）看看ij位置越界了吗？越界不行的，不用讨论了，false

（2）当前ij位置不越界，但是，board[i][j] 字符，压根不等于 word[k]，你咋对应后续的呢？剪枝了，false

（3）那就是说board[i][j] = word[k]
这事，我们可以去别的位置走了，但是走之前，咱需要把board[i][j]令它为别的非字母字符，比如0字符
这样，走完回来我恢复它
避免回头路

比如：ABCDA
走到A，去B之前，需要把A改为0，否则怕你去了B又倒回来走，那就不行了

这样的话，即使你回头，遇到不等于C的字符，你也得返回，这样避免了回头路了

当然，dfs回来，考虑别的情况之前，你要把A恢复

这个就是限制分支，剪枝策略，dfs经常用这招的

好滴，撸代码：

        //复习：这题其实很容易，之前搞太复杂了
        //f(board,i,j,word,k)怎们写？
        //从board的ij出发，能否搞定word从k出发--N位置的所有单词？？？
        //word的k位置之前的所有位置搞定了：0--N-1搞定
        public static boolean f(char[][] board, int i, int j, char[] w, int k){
            //（0）**如果k=N的话**，word已经被搞定了，都走出来了，美滋滋，return true
            if (k == w.length) return true;
            //因为f是：从board的ij出发，能否搞定word从k出发--N位置的所有单词？？？
            //word的k位置之前的所有位置搞定了：0--N-1搞定
            //（1）看看ij位置越界了吗？越界不行的，不用讨论了，false
            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
            //（2）当前ij位置不越界，但是，board[i][j] 字符，压根不等于 word[k]，你咋对应后续的呢？剪枝了，false
            if (board[i][j] != w[k]) return false;
            //（3）那就是说board[i][j] = word[k]
            //这事，我们可以去别的位置走了，但是走之前，咱需要把board[i][j]令它为别的非字母字符，比如0字符
            //这样，走完回来我恢复它
            //避免回头路
            char tmp = board[i][j];
            board[i][j] = '0';//非字母字符
            boolean ans = f(board, i - 1, j, w, k + 1) ||
                    f(board, i + 1, j, w, k + 1) ||
                    f(board, i, j - 1, w, k + 1) ||
                    f(board, i, j + 1, w, k + 1);//上，下，左，右，四个方向有一个OK就行
            //恢复现场
            board[i][j] = tmp;

            return ans;
        }
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

中途tmp记录boardij然后修改它，就是为了防止回头路
这样即使回头也走不通的

---

本题解题主函数

dfs遍历
每一个ij为出发点，看看能走出word来吗，OK吗？？
有其一OK，就true
全部出发都不行？那不好意思

        public boolean existReview(char[][] board, String word) {
            char[] w = word.toCharArray();

            int N = board.length;
            int M = board[0].length;
            //每一个ij为出发点，看看能走出word来吗，OK吗？？
            //有其一OK，就true
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (f(board, i, j, w, 0)) return true;
                }
            }

            //全部出发都不行？那不好意思
            return false;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试：

    public static void test(){
        Solution solution = new Solution();
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','B','S'},
                {'A','D','E','E'},
        };
        String word = "ABCB";

        char[][] board2 = {
                {'A','B','C','E'},
                {'S','F','B','S'},
                {'A','D','E','E'},
        };

        char[][] board3 = {
                {'A','B','C','E'},
                {'S','F','B','S'},
                {'A','D','E','E'},
        };
        System.out.println(solution.exist(board, word));
        System.out.println(solution.exist2(board2, word));
        System.out.println(solution.existReview(board3, word));
    }

    public static void main(String[] args) {
        test();
    }
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

结果很OK：

true
true
true
1
2
3

LeetCode测试：

我之前写的别的版本的代码，有点负责，当时不知道控制word从k–N位置去走，而是用path记录走过的单词是谁，对比word，这样过于复杂

        public boolean exist(char[][] board, String word) {
            //这个，每个ij位置枚举一下，看看有没有，有就好办，没有就算
            //word其实可以考虑加入前缀树，方便我们去cur那条路找去，省得四周多走无效的路来
            //走过不能重复，还是用dfs，临时字符标记来避免，四周处理完回来把现场恢复
            Trie trie = new Trie();
            trie.add(word);
            Node root = trie.root;

            LinkedList<Character> path = new LinkedList<>();//沿路路径加入path
            //遍历ij，找到就返回，否则false
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    boolean ans = process(board, i, j, path, root, word);
                    if (ans) return true;
                }
            }

            return false;//每个位置出发都没有，那over
        }

        //
        public static boolean process(char[][] board, int i, int j,LinkedList<Character> path, Node cur, String word){
            Character tmp = board[i][j];
            if (tmp == '0') return false;

            int index = tmp >='a' && tmp <= 'z' ? tmp - 'a' : tmp - 'A' + 26;
            if (cur.nexts[index] == null) return false;//这条路没有

            cur = cur.nexts[index];//登上ij这里，出发
            path.add(tmp);
            board[i][j] = '0';//标记我走过了，不能回去

            //如果来到了cur，end==1，就找到了,路径又是那个东西
            boolean ans = false;
            if (cur.end == 1 && generatePath(path).equals(word))  {

                ans = true;
                return ans;
            }

            //否则再去看四个方向
            if (i - 1 >= 0) ans |= process(board, i - 1, j, path, cur, word);
            if (i + 1 < board.length) ans |= process(board, i + 1, j, path, cur, word);
            if (j - 1 >= 0) ans |= process(board, i, j - 1, path, cur, word);
            if (j + 1 < board[0].length) ans |= process(board, i, j + 1, path, cur, word);

            board[i][j] = tmp;//board恢复ij这里的情况
            path.pollLast();//path清理现场
            return ans;//返回找的情况
        }

        public static String generatePath(LinkedList<Character> path){
            String ans = "";
            for(Character ch:path) ans += String.valueOf(ch);

            return ans;
        }

        public static class Node{
            public int pass;
            public int end;
            public Node[] nexts;//26+26个大小写字母方向

            public Node(){
                pass = 0;
                end = 0;
                nexts = new Node[52];//初始化啥都没有
            }
        }

        //前缀树极其构建，不需要别的
        public static class Trie{
            public Node root;

            public Trie(){
                root = new Node();
            }

            public void add(String word){
                char[] str = word.toCharArray();
                int path = 0;
                Node cur = root;
                cur.pass++;
                for (int i = 0; i < str.length; i++) {
                    path = str[i] >='a' && str[i] <= 'z' ? str[i] - 'a' : str[i] - 'A' + 26;//把大写字母放入小写之后
                    if (cur.nexts[path] == null) cur.nexts[path] = new Node();//新建这个方向
                    cur = cur.nexts[path];//否则重复利用，往下走
                    //登上这个位置后
                    cur.pass++;
                }
                cur.end++;//这个结尾+1就行
            }
        }


        //貌似不需要word带过去，path啥的
        public boolean exist2(char[][] board, String word) {
            //这个，每个ij位置枚举一下，看看有没有，有就好办，没有就算
            //word其实可以考虑加入前缀树，方便我们去cur那条路找去，省得四周多走无效的路来
            //走过不能重复，还是用dfs，临时字符标记来避免，四周处理完回来把现场恢复
            Trie trie = new Trie();
            trie.add(word);
            Node root = trie.root;

            LinkedList<Character> path = new LinkedList<>();//沿路路径加入path
            //遍历ij，找到就返回，否则false
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    boolean ans = process2(board, i, j, root);
                    if (ans) return true;
                }
            }

            return false;//每个位置出发都没有，那over
        }

        //
        public static boolean process2(char[][] board, int i, int j, Node cur){
            Character tmp = board[i][j];
            if (tmp == '0') return false;

            int index = tmp >='a' && tmp <= 'z' ? tmp - 'a' : tmp - 'A' + 26;
            if (cur.nexts[index] == null) return false;//这条路没有

            cur = cur.nexts[index];//登上ij这里，出发
            board[i][j] = '0';//标记我走过了，不能回去

            //如果来到了cur，end==1，就找到了,路径又是那个东西
            boolean ans = false;
            if (cur.end == 1 )  {
                ans = true;
                return ans;
            }

            //否则再去看四个方向
            if (i - 1 >= 0) ans |= process2(board, i - 1, j, cur);
            if (i + 1 < board.length) ans |= process2(board, i + 1, j, cur);
            if (j - 1 >= 0) ans |= process2(board, i, j - 1, cur);
            if (j + 1 < board[0].length) ans |= process2(board, i, j + 1, cur);

            board[i][j] = tmp;//board恢复ij这里的情况
            return ans;//返回找的情况
        }
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

上面有俩方法哦，没事就不用看了，看我开头那个复习的方法就行

---

总结

提示：重要经验：

1）dfs剪枝策略，这是我们多次说过的事情了，中途不合格，就退出，合格一个OK
2）这个题其实算简单的那种，word从k到结束，这个idea经常是我们要转的，否则代码很负责
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。