题目描述
给定一个二维平板和一个单词，请找出这个单词是否在二维平板中出现。
单词可以由平板中的邻接单元组成，这里的“邻接”定义为上下左右四个方向。
同一个单元上的字母最多只能使用一次。
样例
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定单词 = "ABCCED", return true.
给定单词 = "SEE", return true.
给定单词 = "ABCB", return false.
算法
(DFS) $O(n^23^k)$
在深度优先搜索中，最重要的就是考虑好搜索顺序。
我们先枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。
时间复杂度分析：单词起点一共有 $n^2$ 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 $O(n^23^k)$。
C++ 代码
class Solution {
public:
bool exist(vector<vector<char>>& board, string str) {
for (int i = 0; i < board.size(); i ++ )
for (int j = 0; j < board[i].size(); j ++ )
if (dfs(board, str, 0, i, j))
return true;
return false;
}
bool dfs(vector<vector<char>> &board, string &str, int u, int x, int y) {
if (board[x][y] != str[u]) return false;
if (u == str.size() - 1) return true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
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[a].size()) {
if (dfs(board, str, u + 1, a, b)) return true;
}
}
board[x][y] = t;
return false;
}
};
用st数组判重的写法，大家可以参考下
我觉得这个用st的解法和之前讲过的dfs联系更大一点，赞一个
新开bool数组判重的话要注意不要用vector, 另外dfs函数参数要传引用. 被那个一堆A的样例卡常了。。
对第二点的一点补充：
对内置类型来说，通常传值更高效。
对用于自定义类型来所，传值要经历构造与析构过程，一般比较耗时。
为什么只用一次 board[x][y] = t 而不是每次dfs完都恢复现场呢
board[x][y] = ‘*’; 和board[x][y] = t; 这两句是对应的，位于dfs的两侧。每次只处理当前点(x, y)，for循环里的4个dfs对应的点，在进入dfs后再处理。
if (a >= 0 && a < board.size() && b >= 0 && b < board[a].size())这句话并没有判断当前元素是否被用过，为啥能过通过呢
当前元素已经被改成’*‘了, 不会匹配的. 所以就是多一次递归调用
这里
1 <= word.length <= 10^3, k 是单词的长度 ，$ 3 ^ k$不会爆时间复杂度吗？暴搜问题比较特殊，一般不考虑时间复杂度会爆掉的情况。
y总这题空间复杂度怎么计算啊，递归的系统栈怎么算
递归的空间复杂度取决的最大递归层数，所以这题的空间复杂度是 $O(k)$，$k$ 是被查找的单词长度。
提交时间：1 分钟之前
执行出错信息：
AddressSanitizer: heap-buffer-overflow on address 0x6020000026b2 at pc 0x000000406407 bp 0x7ffca1bac460 sp 0x7ffca1bac458
最后执行的输入：
[[“b”,”b”],[“a”,”b”],[“b”,”a”]]
“a”
这个输入数据里的所有引号都是中文的，得改成英文的才可以：
大佬，这个题解没过啊
我试了一下可以AC啊
我们也可以不用bool 数组来判重的，因为given word is made up with letters, so after we visit that cell, we can set its value to a special character, for example: ‘0’, as long as this special character is not a letter, it won’t match with the remain letters in the given word, in other words, it won’t be visited a second time. And when we backtrack, we can set its original value back again. ^_^
不错！这样可以省掉一部分空间开销
写成vector[HTML_REMOVED]> 过不了，写成int [4][4]就过了，坑啊，这题