Leetcode79单词搜索

题目

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

分析

步骤一，先遍历寻找到开始的位置，就是一个普通的双层遍历即可；
步骤二，从开头位置开始，进行递归遍历搜索。
如下图，想要寻找单词“FCSEE”,首先在步骤一中找到F字母在（1,1）位置；
先寻找上边，上边找不到就找左边，左边找不到就找下边，下边找不到就找右边；如果四边都找不到，就返回false，继续寻找。
需要把每个寻找到的字符进行替换成‘0’，防止重复使用了某个字符；四边都寻找过后，把字符替换回来；
下图展示了寻找的过程，如果匹配，则字符变成黑色并替换成0；如果匹配不通过，则字符变成红色。

image.png

代码

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size(),m = board[0].size();
        //找到开头的节点
        for(int i=0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(board[i][j] == word[0])
                    //如果找到了，就立即返回
                    if(search(board,word,i,j))
                        return true;
            }
        }
        return false;
    }
    
    bool search(vector<vector<char>>& board,string word,int x,int y){
        //如果word的长度为1，证明不需要往下找了，返回True
        if(word.size() == 1)
            return true;
        char a = board[x][y];
        //把已经使用过的数组替换掉
        board[x][y] = '0';
        bool res = false;
        //先找上面，然后左边，然后下面，然后右边
        if(x>0 && board[x-1][y]==word[1])
            res = search(board,word.substr(1),x-1,y);
        if(!res && y>0 && board[x][y-1]==word[1])
            res = search(board,word.substr(1),x,y-1);
        if(!res && x+1<board.size() && board[x+1][y]==word[1])
            res = search(board,word.substr(1),x+1,y);
        if(!res && y+1<board[0].size() && board[x][y+1]==word[1])
            res = search(board,word.substr(1),x,y+1);
        //找完之后数组要替换回来
        board[x][y] = a;
        //返回最后一次寻找的结果
        return res;
    }
};