LeetCode 79. 单词搜索
难度:middle\color{orange}{middle}middle
题目描述
给定一个 mxnm x nmxn 二维字符网格 boardboardboard 和一个字符串单词 wordwordword 。如果 wordwordword 存在于网格中,返回 truetruetrue ;否则,返回 falsefalsefalse 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 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.lengthm == board.lengthm==board.length
- n=board[i].lengthn = board[i].lengthn=board[i].length
- 1<=m,n<=61 <= m, n <= 61<=m,n<=6
- 1<=word.length<=151 <= word.length <= 151<=word.length<=15
- boardboardboard 和 wordwordword 仅由大小写英文字母组成
进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 boardboardboard 更大的情况下可以更快解决问题?
算法
(递归)
在深度优先搜索中,最重要的就是考虑好搜索顺序。
我们先枚举单词的起点,然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母,以避免重复使用字符。
复杂度分析
-
时间复杂度:O(n23k)O(n^2 3^k)O(n23k),单词起点一共有 n2n^2n2 个,单词的每个字母一共有上下左右四个方向可以选择,但由于不能走回头路,所以除了单词首字母外,仅有三种选择。所以总时间复杂度是 O(n23k)O(n^2 3^k)O(n23k)
-
空间复杂度 : O(n)O(n)O(n)
C++ 代码
class Solution {
public:bool exist(vector<vector<char>>& board, string word) {for (int i = 0; i < board.size(); i ++) {for (int j = 0; j < board[0].size(); j ++) {if (dfs(board, word, 0, i, j)) return true;}}return false;}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};bool dfs(vector<vector<char>>& board, string& word, int u, int x, int y) {if (board[x][y] != word[u]) return false;if (u == word.size() - 1) return true;char t = board[x][y];board[x][y] = '.';for (int i = 0; i < 4; i ++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.')continue;if (dfs(board, word, u + 1, a, b)) return true;}board[x][y] = t;return false;}
};