LeetCode 算法：单词搜索 c++

原题链接🔗：单词搜索
难度：中等⭐️⭐️

题目

给定一个 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 仅由大小写英文字母组成

题解

1. 解题思路：

LeetCode上的“单词搜索”问题是一个典型的回溯算法问题。这个问题的基本思路是在一个二维字符数组中搜索一个给定的单词，单词可以按任意方向（水平、垂直、对角线）进行搜索。以下是解题的基本步骤和思路：

• 问题描述

  • 给定一个二维字符数组 board 和一个单词 word，找出 word 是否存在于 board 中。单词必须按字母顺序通过相邻的单元格（水平、垂直或对角线）拼写，并且只能使用每个单元格一次。

• 解题思路

  • 定义搜索函数：定义一个递归函数 search，该函数接收当前位置 (i, j) 和当前单词的索引 k。
  • 检查当前字符：如果当前位置的字符与单词的当前字符不匹配，则返回 false。
  • 检查边界：如果 i 或 j 超出数组边界，或者当前字符不匹配，则返回 false。
  • 标记访问：将当前位置的字符暂时替换为一个特殊字符（如 ‘#’），以防止重复访问。
  • 递归搜索：在当前位置的四个方向（上、下、左、右）递归调用 search 函数。
  • 回溯：无论搜索是否成功，都需要将当前位置的字符恢复为原始字符，以便其他路径可以访问。
  • 返回结果：如果搜索到单词的最后一个字符，返回 true。

2. c++ demo：

#include <vector>
#include <string>
#include <iostream>

using namespace std;
class Solution {
public:
    bool exist(vector<vector<char>>& board, const string& word) {
        int m = board.size();
        int n = board[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool dfs(vector<vector<char>>& board, const string& word, int x, int y, int k) {
        if (k == word.size()) return true; // 单词搜索完成
        if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size() || board[x][y] != word[k]) return false; // 越界或字符不匹配

        char temp = board[x][y]; // 标记访问
        board[x][y] = '#';

        // 搜索四个方向
        if (dfs(board, word, x + 1, y, k + 1) || dfs(board, word, x - 1, y, k + 1) ||
            dfs(board, word, x, y + 1, k + 1) || dfs(board, word, x, y - 1, k + 1)) {
            return true;
        }

        board[x][y] = temp; // 回溯
        return false;
    }
};

int main() {
    Solution solution;
    vector<vector<char>> board = {
        {'A', 'B', 'C', 'E'},
        {'S', 'F', 'C', 'S'},
        {'A', 'D', 'E', 'E'}
    };
    string word = "ABC";

    if (solution.exist(board, word)) {
        std::cout << "Word found in the board." << std::endl;
    }
    else {
        std::cout << "Word not found in the board." << std::endl;
    }

    return 0;
}

• 输出结果：

Word found in the board.

3. 代码仓库地址： exist