给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
示例1
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true示例 2：
示例2.jpg输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true示例 3：
示例3.jpg输入：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 仅由大小写英文字母组成
分析题目，与迷宫搜索类似，使用深度优先及回溯算法查找是否匹配字符串。在深度优先算法中可以使用递归的方式，但这里使用堆栈来实现，更好的理解查找过程。
- 首先定义堆栈中保存访问节点数据
struct Point {
int x;
int y;
Point(int i, int j) {
x = i;
y = j;
}
};
- 在遍历二维数组时，我们需要记录是否已访问该位置，所以，需要定义一个二维数组标签，初始化为0。
void initFlag(vector<vector<int>> &flag, int m, int n) {
flag.resize(m);
for (int i = 0; i < m; ++i) {
flag[i].resize(n);
}
}
- 同时，我们仍然利用该二维数组标签记录该位置处的访问情况。如向右、向左、向上还是向下，在回溯时我们判断访问该位置的下一个位置时使用。如果4个方向都被访问了，则出栈。
if (flag[t.x][t.y] == 1) {
flag[t.x][t.y] = 2;
if (t.y + 1 < n && flag[t.x][t.y + 1] == 0 && board[t.x][t.y + 1] == word[size]) {
flag[t.x][t.y + 1] = 1;
stk.push(Point(t.x, t.y + 1));
}
} else if (flag[t.x][t.y] == 2) {
flag[t.x][t.y] = 3;
if (t.y - 1 >= 0 && flag[t.x][t.y - 1] == 0 && board[t.x][t.y - 1] == word[size]) {
flag[t.x][t.y - 1] = 1;
stk.push(Point(t.x, t.y - 1));
}
} else if (flag[t.x][t.y] == 3) {
flag[t.x][t.y] = 4;
if (t.x - 1 >= 0 && flag[t.x - 1][t.y] == 0 && board[t.x - 1][t.y] == word[size]) {
flag[t.x - 1][t.y] = 1;
stk.push(Point(t.x - 1, t.y));
}
} else if (flag[t.x][t.y] == 4) {
flag[t.x][t.y] = 5;
if (t.x + 1 < m && flag[t.x + 1][t.y] == 0 && board[t.x + 1][t.y] == word[size]) {
flag[t.x + 1][t.y] = 1;
stk.push(Point(t.x + 1, t.y));
}
} else {
flag[t.x][t.y] = 0;
stk.pop();
}
- 很久没有练习深度优先与回溯的算法就有点忘了，所以在此记录一下该实现过程。完整代码实现如下：
struct Point {
int x;
int y;
Point(int i, int j) {
x = i;
y = j;
}
};
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
if (m * n < word.length()) {
return false;
}
stack<Point> stk;
vector<vector<int>> flag;
initFlag(flag, m, n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] != word[0]) {
continue;
}
stk.push(Point(i, j));
flag[i][j] = 1;
while (!stk.empty() && stk.size() < word.length()) {
int size = stk.size();
Point &t = stk.top();
if (flag[t.x][t.y] == 1) {
flag[t.x][t.y] = 2;
if (t.y + 1 < n && flag[t.x][t.y + 1] == 0 && board[t.x][t.y + 1] == word[size]) {
flag[t.x][t.y + 1] = 1;
stk.push(Point(t.x, t.y + 1));
}
} else if (flag[t.x][t.y] == 2) {
flag[t.x][t.y] = 3;
if (t.y - 1 >= 0 && flag[t.x][t.y - 1] == 0 && board[t.x][t.y - 1] == word[size]) {
flag[t.x][t.y - 1] = 1;
stk.push(Point(t.x, t.y - 1));
}
} else if (flag[t.x][t.y] == 3) {
flag[t.x][t.y] = 4;
if (t.x - 1 >= 0 && flag[t.x - 1][t.y] == 0 && board[t.x - 1][t.y] == word[size]) {
flag[t.x - 1][t.y] = 1;
stk.push(Point(t.x - 1, t.y));
}
} else if (flag[t.x][t.y] == 4) {
flag[t.x][t.y] = 5;
if (t.x + 1 < m && flag[t.x + 1][t.y] == 0 && board[t.x + 1][t.y] == word[size]) {
flag[t.x + 1][t.y] = 1;
stk.push(Point(t.x + 1, t.y));
}
} else {
flag[t.x][t.y] = 0;
stk.pop();
}
}
if (stk.size() >= word.length()) {
return true;
}
}
}
return false;
}
void initFlag(vector<vector<int>> &flag, int m, int n) {
flag.resize(m);
for (int i = 0; i < m; ++i) {
flag[i].resize(n);
}
}
};
