当前位置：首页 > news >正文

LeetCode 算法：单词搜索 c++

news 来源：原创 2024/9/20 13:55:03

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

题目

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

题解

解题思路：

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

问题描述

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

解题思路

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

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