79.单词搜索

79. 单词搜索

给定一个 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

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

C++

class Solution {
public:
    bool tag = false;
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0) return false;
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> used(m, vector<bool>(n , false));
        for(int i = 0; i < m; i ++){
           for(int j = 0; j < n; j ++){
               backtracking(board, word, 0, i, j, used);
               if(tag) return tag;
           }
       }
       return tag;
    }
    
    //传引用直接在原始位置操作，不需要进行新建变量与赋值，节省了代码运行的空间与时间开销
    void backtracking(vector<vector<char>>& board, string word, int idx, int r, int c, vector<vector<bool>>& used){  
        if(r < 0 || r >= board.size() || c < 0 || c >= board[0].size() 
        || used[r][c] == true || board[r][c] != word[idx]) return;

        if(idx == word.size() - 1) {
            tag = true;
            return;
        }

        used[r][c] = true;
        backtracking(board, word, idx + 1, r + 1, c, used);
        backtracking(board, word, idx + 1, r, c + 1, used);
        backtracking(board, word, idx + 1, r - 1, c, used);
        backtracking(board, word, idx + 1, r, c - 1, used);
        used[r][c] = false; // 回撤是因为这样就不用在main函数里每次循环new一个全0的used数组出来
    }
};