题目描述
给定一个 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
算法
(DFS) $O(nm * 3^k)$
在深度优先搜索中,最重要的就是考虑好搜索顺序。
我们先枚举单词的起点,然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母,以避免重复使用字符。
时间复杂度分析:单词起点一共有n * m
个,单词的每个字母一共有上下左右四个方向可以选择,但由于不能走回头路,所以除了单词首字母外,仅有三种选择。所以总时间复杂度是$O(nm * 3^k)$
C++ 代码
class Solution {
public:
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) return false;
n = board.size(), m = board[0].size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (dfs(board, word, i, j, 0))
return true;
return false;
}
bool dfs(vector<vector<char>>& board, string& word, int x, int y, int u)
{
if (board[x][y] != word[u]) return false;
if (u == word.size() - 1)
{
cout << "hh" << endl;
return true;
}
board[x][y] = '.';
for (int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m)
if (dfs(board, word, a, b, u + 1))
return true;
}
board[x][y] = word[u];
return false;
}
};