LeetCode—79.单词搜索[Word Search]——分析及代码[C++]

一、题目二、分析及代码1. 深度优先搜索 + 回溯法（1）思路（2）代码（3）结果 三、其他

一、题目

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

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

示例:

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.

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

二、分析及代码

1. 深度优先搜索 + 回溯法

（1）思路

寻找第一个符合条件的字符：可以通过遍历找到； 之后寻找下一个符合条件的字符：从当前字符出发，一共只有上、下、左、右 4 个方向可扩展，通过深度优先搜索 + 回溯 可以递归处理。 避免重复： 1）用另一个同样大小的二维矩阵记录字符使用情况； 2）寻找下一个符合条件的字符时，无需向刚刚的来源方向寻找（有方法 1 后，可取消这步判断）。

（2）代码

class Solution { vector<vector<char>> board; vector<vector<int>> usage;//记录字符使用情况 string word; int tarlen;//word长度 int n, m;//board行、列数 public: bool exist(vector<vector<char>>& board, string word) { this->word = word; tarlen = word.size(); if (tarlen == 0) return true; this->board = board; if (board.size() == 0) return false; int dire = -1;//0:up, 1:down, 2:left, 3:right；有了usage矩阵后，实际上也可取消方向的判断 n = board.size(); m = board[0].size(); usage = vector<vector<int>>(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) {//遍历寻找第一个字符 for (int j = 0; j < m; j++) if (board[i][j] == word[0]) { usage[i][j] = 1; if (backtrack(i, j, 1, dire)) return true; usage[i][j] = 0; } } return false; } bool backtrack(int posi, int posj, int count, int dire) {//回溯寻找后续字符 if (count == tarlen)//完成单词搜索 return true; if (dire != 0 && posi > 0 && usage[posi - 1][posj] == 0 && board[posi - 1][posj] == word[count]) {//向上寻找 usage[posi - 1][posj]++; if (backtrack(posi - 1, posj, count + 1, 1)) return true; usage[posi - 1][posj]--; } if (dire != 1 && posi < n - 1 && usage[posi + 1][posj] == 0 && board[posi + 1][posj] == word[count]) {//向下寻找 usage[posi + 1][posj]++; if (backtrack(posi + 1, posj, count + 1, 0)) return true; usage[posi + 1][posj]--; } if (dire != 2 && posj > 0 && usage[posi][posj - 1] == 0 && board[posi][posj - 1] == word[count]) {//向左寻找 usage[posi][posj - 1]++; if (backtrack(posi, posj - 1, count + 1, 3)) return true; usage[posi][posj - 1]--; } if (dire != 3 && posj < m - 1 && usage[posi][posj + 1] == 0 && board[posi][posj + 1] == word[count]) {//向右寻找 usage[posi][posj + 1]++; if (backtrack(posi, posj + 1, count + 1, 2)) return true; usage[posi][posj + 1]--; } return false; } };

（3）结果

执行用时 ：20 ms, 在所有 C++ 提交中击败了 98.80% 的用户； 内存消耗 ：10.9 MB, 在所有 C++ 提交中击败了 80.55% 的用户。

三、其他

暂无。