HHot 100C++ 图解

79. 单词搜索

一句话套路网格 DFS + 占位符标记,回溯时还原

题目描述

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

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

 

示例 1:

输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出:true

示例 2:

输入:board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出:true

示例 3:

输入: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 仅由大小写英文字母组成

 

进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

思路

时间O(mn·3^L)(每步最多 3 个新方向)
空间O(L)

思路

网格 DFS + 回溯。用「临时把格子改成一个非字母占位符」代替 visited 数组,省空间;

但必须还原,否则会破坏入参(多次调用/多次分支都会踩这个坑)。

剪枝

先统计词频,若某个字符在 board 里不够多,直接返回 false(高频加分项,见下方代码)。

图解

j0 j1 j2 j3 i0 A B C E i1 S F C S i2 A D E E
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/10_backtracking.cpp34 行
namespace lc0079 {
class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    if (board.empty() || board[0].empty()) return false;  // 空盘搜不出任何东西(题面保证 m,n ≥ 1)
    // 剪枝:词频不够就根本不用搜(面试里这一句常常是真正的加分点)
    int need[26] = {};
    for (char c : word) ++need[(unsigned char)c - 'A'];
    for (const auto& row : board)
      for (char c : row)
        if (c >= 'A' && c <= 'Z') --need[(unsigned char)c - 'A'];
    for (int i = 0; i < 26; ++i)
      if (need[i] > 0) return false;
    const int R = (int)board.size(), C = (int)board[0].size();
    for (int i = 0; i < R; ++i)
      for (int j = 0; j < C; ++j)
        if (dfs(board, word, i, j, 0, R, C)) return true;
    return false;
  }

 private:
  static bool dfs(vector<vector<char>>& b, const string& w, int i, int j, int k, int R, int C) {
    if (k == (int)w.size()) return true;             // 整个词都匹配上了
    if (i < 0 || j < 0 || i >= R || j >= C) return false;
    if (b[i][j] != w[k]) return false;
    char saved = b[i][j];
    b[i][j] = '#';  // 占位:同一格不能在一条路径里用两次
    bool found = dfs(b, w, i + 1, j, k + 1, R, C) || dfs(b, w, i - 1, j, k + 1, R, C) ||
                 dfs(b, w, i, j + 1, k + 1, R, C) || dfs(b, w, i, j - 1, k + 1, R, C);
    b[i][j] = saved;  // 回溯还原 —— 漏了这行,本格被永久标成 '#',其他分支再用它就得到假阴性
    return found;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q79_word_search10 行
lc0079::Solution s;
vector<vector<char>> b{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
CHECK_TRUE(s.exist(b, "ABCCED"));
CHECK_TRUE(s.exist(b, "SEE"));
CHECK_FALSE(s.exist(b, "ABCB"));   // 盘上只有一个 B,而且已经被走过 —— 同一格不能在一条路径里用两次
CHECK_FALSE(s.exist(b, "ABCEZ"));  // 词里有 board 上不存在字符
CHECK_TRUE(s.exist(b, "A"));
CHECK_FALSE(s.exist(b, "AAAA"));  // 盘上只有 2 个 A,词频剪枝直接拒掉
vector<vector<char>> emptyBoard;
CHECK_FALSE(s.exist(emptyBoard, "A"));  // 空盘:不守卫就是 board[0] 越界

↑↓ 选择↵ 打开/ 随时唤起