题目概览

题解

采用深度优先搜索，以及回溯的思想，回溯 (上下左右四个方向找，找到完整的word后，则返回true。注意边界条件，“超出边界"或"所在位置元素不满足条件” 则返回false)
（假设行为i = board.size() = rows，列为j = board[0].size() = cols）

超出边界的条件为：

1. i < 0
2. i >= rows
3. j < 0
4. j >= cols

不相等的条件为：
board[i][j] != word[k]

同时把遍历正确的字符给标记成\0，这样就可以防止重复遍历，将减少复杂度。同时，返回true后，将复原标记好的字符，即board[i][j] = word[k]。

关于实现4个方向的搜索，可以采用bool res = dfs(board, word, k + 1, i + 1, j) || dfs(board, word, k + 1, i - 1, j) || dfs(board, word, k + 1, i, j - 1) || dfs(board, word, k + 1, i, j + 1);此行代码，因为$k$朝哪个方向进行搜索都是要加一的，而$i$和$j$的加减则是分别代表左右以及上下。（行列的变化）

Code

class Solution {
public:
    bool dfs(vector<vector<char>>& board, string word, int k, int i, int j);
    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) == true)
                {
                    return true;
                }
            }
        }
        return false;
    }
};

bool Solution::dfs(vector<vector<char>>& board, string word, int k, int i, int j)
{
    int rows = board.size();
    int cols = board[0].size();
    if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != word[k])
    {
        return false;
    }
    if (k == word.size() - 1)
    {
        return true;
    }
    board[i][j] = '\0';
    bool res = dfs(board, word, k+1, i, j-1) || dfs(board, word, k+1, i, j+1) || dfs(board, word, k+1, i+1, j) || dfs(board, word, k+1, i-1, j) ;
    board[i][j] = word[k];
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//解析版
// 回溯  (上下左右四个方向找，"找到完整的word后" 则返回true。注意边界条件，"超出边界"或"所在位置元素不满足条件" 则返回false)
class Solution {
public:
    bool dfs(vector<vector<char>>& board, string word, int k, int i, int j);

    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i) {               // 矩阵中每个字符 都作为起始字符 来开始寻找word,二维数组当中size()就是行数
            for (int j = 0; j < board[0].size(); ++j) {         //二维数组的[0].size()为列数
                    if (dfs(board, word, 0, i, j) == true) return true;        // 只有在找到完整的word后 才会返回true （也就是确认完最后一个字符） // 从k=0开始
            }
        }
        return false;//否则就是返回false
    }
};

bool Solution::dfs(vector<vector<char>>& board, string word, int k, int i, int j) {
    int rows = board.size();
    int cols = board[0].size();
    if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;  // 超出边界或所在位置元素不满足条件 则返回false
    if (k == word.size() - 1) return true;  // "找到完整的word后" 则返回true（k为 word最后一个字符的下标，不要被二维数组弄混淆了，k是在string word当中字符的下标）
    //
    board[i][j] = '\0';    // 向下搜索的时候，记得把当前满足条件的元素board[i][j]设为'\0'，表示该位置 被访问过
    bool res = dfs(board, word, k + 1, i + 1, j) || dfs(board, word, k + 1, i - 1, j) ||        // 四个方向搜索！(约束条件都在前面过滤掉了！妙！)
        dfs(board, word, k + 1, i, j - 1) || dfs(board, word, k + 1, i, j + 1);                 
    board[i][j] = word[k];    // 因为是递归调用，所以函数会返回，也就是回溯！之前在该位置标记过，现在要恢复原来的值
     // 为什么要恢复？ 因为从该位置向下的路径都搜索完了，"继续从上一个位置 选择其它路径开始搜索"，
     //所以之前从该位置向下搜索的路径 "现在都没搜索过"，所以该路径上所有位置的标记 都要清除。
    return res; // 又因为是在原board上 覆盖标记的，所以要恢复原board该位置上的值，从而"继续从上一个位置 选择其它路径开始搜索"，并且不会对接下来的搜索 造成困扰
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结果