LeetCode79.单词搜索 DFS+剪枝

解题思路

DFS+剪枝
刚开始做的时候没有进行剪枝，只是暴力DFS，时间1400ms非常糟糕
进DFS前，进行一次剪枝，枚举到word第一个字符时进DFS并在book数组内记录已经访问。

递归结束后记得把访问标记取消

for(int i = 0; i < board.size(); i++)
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if(board[i][j] == word[0])
                {
                    book[i][j] = true;//标记拿下该字符
                    dfs(i, j, board, word);//递归
                    book[i][j] = false;//回溯 回到上一状态
                    n--;//回溯 回到上一状态
                    if(flag) return true;//找到答案 返回true
                }
            }
        }

DFS主逻辑内 先把当前位置字符拿下，即++n,如果n的长度等于word的长度，那必然是我们要的答案，因为DFS内的剪枝 *** 作保证了只有我们要的字符才会进入下一次递归。

然后枚举四个方向，判断下一位置的有效性。

注意这里不是只进行越界判断，而要再加一层剪枝

if(word[n] != board[nextx][nexty]) continue;//剪枝

剪枝 *** 作保证了已找到字符的正确性，所以只用n记录长度，而不用temp字符串记录，最后再检验正确性。

代码

class Solution
{
public:
    bool flag = false;//是否找到答案
    int n = 0;//当年已找到的答案长度
    bool book[7][7] = {false};//记录已访问位置的数字组
    const int dir[4][2] = {
            {0,  1},
            {1,  0},
            {0,  -1},
            {-1, 0}
    };//四个方向

    void dfs(int x, int y, vector<vector<char>> &board, string &word)
    {

        if(flag) return;//如果已经找到答案直接返回
        if(++n == word.size())//判断当前位置拿下后是不是word
        {
            flag = true;
            return;
        }
        for(int k = 0; k < 4; k++)//枚举四个方向
        {

            int nextx = x + dir[k][0];
            int nexty = y + dir[k][1];
            if(nextx < 0 || nexty < 0 || nextx >= board.size() || nexty >= board[0].size() || book[nextx][nexty])
            {
                continue;
            }//越界判断
            if(word[n] != board[nextx][nexty]) continue;//剪枝

            book[nextx][nexty] = true;//拿下该字符
            dfs(nextx, nexty, board, word);//递归
            if(flag) return;
            n--;//回溯 回到上一状态
            book[nextx][nexty] = false;//回溯 回到上一状态
        }
    }

    bool exist(vector<vector<char>> &board, string &word)
    {
        char c = word[0];
        for(int i = 0; i < board.size(); i++)
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if(board[i][j] == word[0])
                {
                    book[i][j] = true;//标记拿下该字符
                    dfs(i, j, board, word);//递归
                    book[i][j] = false;//回溯 回到上一状态
                    n--;//回溯 回到上一状态
                    if(flag) return true;//找到答案 返回true
                }
            }
        }
        return false;
    }
};