c++-c++编程基础之leetcode题解第79题单词搜索.zip资源-CSDN下载

共1个文件

md：1个

需积分: 50 156 浏览量 2024-04-16 08:17:15 上传评论收藏 2KB ZIP 举报

在本压缩包中，主题聚焦于C++编程基础与LeetCode题解，特别是关于第79题“单词搜索”（Word Search）。LeetCode是一个在线平台，它提供了许多编程题目，帮助开发者提升算法技能和问题解决能力。让我们深入探讨C++编程语言的基础知识，以及如何利用C++解决LeetCode中的单词搜索问题。 C++是一种静态类型的、编译式的、通用的、大小写敏感的、不仅支持过程化编程，也支持面向对象编程的程序设计语言。它的强大之处在于高效、灵活和丰富的库支持，使得它成为开发各种复杂软件的理想选择，包括算法实现和数据结构操作。在LeetCode的第79题“单词搜索”中，问题通常描述为：给定一个二维字符网格`board`和一个单词列表`words`，找出所有给定单词在网格中的隐藏路径。每个单词必须按照字母顺序沿着水平、垂直或对角线方向相邻的单元格内的字母构成，且不允许回溯。这是一道典型的深度优先搜索（DFS）问题，也可以通过广度优先搜索（BFS）来解决。在C++中，我们可以先定义一个二维数组来表示字符网格，然后使用一个递归函数或者栈来实现DFS。以下是使用DFS的C++代码框架： ```cpp bool exist(vector<vector<char>>& board, string word) { if (board.empty() || board[0].empty()) return false; int m = board.size(), n = board[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (dfs(board, i, j, word, 0, visited)) return true; } } return false; } bool dfs(vector<vector<char>>& board, int i, int j, string& word, int index, vector<vector<bool>>& visited) { // 实现递归逻辑 } ``` 在`dfs`函数中，我们需要检查当前位置是否合法，然后比较字符是否匹配，如果匹配则标记为已访问，并继续搜索下一个字符；如果不匹配或超出边界，则返回false。递归过程中，我们需要处理回溯情况，即当找不到匹配的下一个字符时，将当前位置标记为未访问，回退到上一状态。此外，为了优化性能，我们通常会将`board`和`visited`数组设置为全局变量，避免每次调用`dfs`时的拷贝开销。同时，可以考虑使用哈希表来存储单词列表，提高查找效率。这个压缩包中的内容涵盖了C++编程基础，如二维数组操作、递归和回溯算法，以及LeetCode中的经典问题——单词搜索。通过学习和实践这一题解，开发者能够进一步掌握C++语言的使用，并提高解决实际问题的能力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第79题单词搜索.zip （1个子文件）

c++_c++编程基础之leetcode题解第79题单词搜索

README.md 4KB

# [79. Word Search (Medium)](https://leetcode.com/problems/word-search/) Given an <code>m x n</code> grid of characters <code>board</code> and a string <code>word</code>, return <code>true</code> if <code>word</code> exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.   Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;"> <pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true </pre> Example 2: <img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;"> <pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true </pre> Example 3: <img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;"> <pre>Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false </pre>   Constraints: <ul> <li><code>m == board.length</code></li> <li><code>n = board[i].length</code></li> <li><code>1 <= m, n <= 6</code></li> <li><code>1 <= word.length <= 15</code></li> <li><code>board</code> and <code>word</code> consists of only lowercase and uppercase English letters.</li> </ul>   Follow up: Could you use search pruning to make your solution faster with a larger <code>board</code>? **Companies**: [Amazon](https://leetcode.com/company/amazon), [Microsoft](https://leetcode.com/company/microsoft), [Snapchat](https://leetcode.com/company/snapchat), [Bloomberg](https://leetcode.com/company/bloomberg), [Twitter](https://leetcode.com/company/twitter), [Facebook](https://leetcode.com/company/facebook), [Apple](https://leetcode.com/company/apple), [Goldman Sachs](https://leetcode.com/company/goldman-sachs), [Cisco](https://leetcode.com/company/cisco), [Google](https://leetcode.com/company/google), [Adobe](https://leetcode.com/company/adobe), [VMware](https://leetcode.com/company/vmware), [Cruise Automation](https://leetcode.com/company/cruise-automation), [ByteDance](https://leetcode.com/company/bytedance), [Bolt](https://leetcode.com/company/bolt) **Related Topics**: [Array](https://leetcode.com/tag/array/), [Backtracking](https://leetcode.com/tag/backtracking/), [Matrix](https://leetcode.com/tag/matrix/) **Similar Questions**: * [Word Search II (Hard)](https://leetcode.com/problems/word-search-ii/) ## Solution 1. Backtracking ```cpp // OJ: https://leetcode.com/problems/word-search/ // Author: github.com/lzl124631x // Time: O(MN * 4^K) // Space: O(K) class Solution { public: bool exist(vector<vector<char>>& A, string s) { int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; function<bool(int, int, int)> dfs = [&](int x, int y, int i) { if (x < 0 || x >= M || y < 0 || y >= N || A[x][y] != s[i]) return false; if (i + 1 == s.size()) return true; char c = A[x][y]; A[x][y] = 0; for (auto &[dx, dy] : dirs) { if (dfs(x + dx, y + dy, i + 1)) return true; } A[x][y] = c; return false; }; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (dfs(i, j, 0)) return true; } } return false; } }; ```

评论收藏

内容反馈