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 dfs(vector<vector<char>>& board, string word, int row, int col, int idx)
    {
        // 递归结束条件
        if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size())
            return false;        
        if(board[row][col] != word[idx])
            return false;

        if(idx == word.size() - 1)
            return true;
        board[row][col] = '0';            // 将当前位置的元素修改为 0，使得后续不会被重复查找
        bool left = dfs(board, word, row, col - 1, idx + 1);
        bool right = dfs(board, word, row, col + 1, idx + 1);
        bool up = dfs(board, word, row - 1, col, idx + 1);
        bool down = dfs(board, word, row + 1, col, idx + 1);
        board[row][col] = word[idx];    // 回溯，将当前位置改回原值
        return left || right || up || down;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0 || board[0].size() == 0 || word.size() == 0)
            return false;

        int rows = board.size();
        int cols = board[0].size();
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                if(board[i][j] == word[0] && dfs(board, word, i, j, 0) == true)
                    return true;
            }
        }
        return false;
    }
};

执行结果：

执行结果：通过

执行用时：532 ms, 在所有 C++ 提交中击败了 35.10% 的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了 31.25% 的用户