leetcode：79. 单词搜索

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

解答 & 代码

DFS 深度优先遍历，递归回溯

class Solution {
private:
    bool backTrack(vector<vector<char>>& board, int row, int col, string word, int idx)
    {
        int rows = board.size();
        int cols = board[0].size();
        // 递归结束条件 1：已搜索到完整的单词，直接返回 true
        if(idx == word.size())
            return true;
        // 递归结束条件 2：网格下标越界，直接返回 false
        if(row < 0 || row >= rows || col < 0 || col >= cols)
            return false;
        // 递归结束条件 2：当前网格和单词字符不匹配，直接返回 false
        if(board[row][col] != word[idx])
            return false;
        // 选择：选择当前网格，并修改为 '0'，以避免被重复选择
        board[row][col] = '0';
        // 递归回溯：上、下、左、右
        bool up = backTrack(board, row - 1, col, word, idx + 1);
        bool down = backTrack(board, row + 1, col, word, idx + 1);
        bool left = backTrack(board, row, col - 1, word, idx + 1);
        bool right = backTrack(board, row, col + 1, word, idx + 1);
        // 撤销选择：将当前网格恢复为原字符
        board[row][col] = word[idx];
        return up || down || left || right;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0)
            return true;
        if(board.size() == 0 || board[0].size() == 0)
            return false;
        int rows = board.size();
        int cols = board[0].size();
        for(int row = 0; row < rows; ++row)
        {
            for(int col = 0; col < cols; ++col)
            {
                if(board[row][col] == word[0] && 
                    backTrack(board, row, col, word, 0) == true)
                    return true;
            }
        }
        return false;
    }
};

复杂度分析：设网格大小为 M×N，单词长度 L

• 时间复杂度 ：遍历 MN 个网格，假设刚好 MN 个网格都和单词首字符相等，则需要进行 MN 次 dfs 查找。每次 dfs 查找，除了第一次可以进入 4 个分支（但上、左也会越界直接返回），其余时间最多都只能进入 3 个分支（不会返回上一步的位置，因为已经被被修改为 '0' 以避免重复选择），字符串长度 L，每个位置有 3 个选择，因此时间复杂度
• 空间复杂度 O(L)：递归栈深度

执行结果：

执行结果：通过
执行用时：532 ms, 在所有 C++ 提交中击败了 35.56% 的用户
内存消耗：7.7 MB, 在所有 C++ 提交中击败了 89.55% 的用户