【一天一道LeetCode】#79. Word Search

一天一道LeetCode

（一）题目

（二）解题

本题大意：在一个字母矩阵中搜索指定的单词，要求矩阵中相邻的字母（上下左右）连接起来组成指定的单词，矩阵中的字母不允许重复使用。

解题思路：

1、采用回溯法和动态规划来解决

2、每次搜索到首字母后就向四个方向继续搜索，知道连接起来组成整个指定单词为止

3、注意字母不能重复搜索，需要用一个矩阵来标记此次搜索过的单词

下面来看具体代码：

class Solution {
public:
    bool isExist = false;
    bool exist(vector<vector<char>>& board, string word) {
        if(word == "") return true;//单词为空的特殊情况
        int row = board.size();
        if(row == 0) return false;
        int col = board[0].size();
        vector<vector<bool>> isSearch;
        for(int i = 0 ; i < row ; i++)//初始化用来标记已搜索过字母的矩阵
        {
            vector<bool> temp(col,false);
            isSearch.push_back(temp);
        }
        for (int i = 0; i < row;i++)
        {
            for (int j = 0; j < col;j++)
            {
                if(board[i][j] == word[0]) {//如果找到首字母就开始从四个方向搜索
                    backTraceExist(board, word, 0,i, j, row ,col ,isSearch);
                }
            }
        }
        return isExist;
    }
    void backTraceExist(vector<vector<char>>& board, string word , int count ,int x , int y, int& row,int& col,vector<vector<bool>>& isSearch)
    {
        if(board[x][y] == word[count]) count++;//如果相等
        else{
            return;
        }
        if(count == word.length())//结束标志
        {
            isExist = true;
            return;
        }
        if(!isExist){
            isSearch[x][y] = true;//找过的字母记得标记起来
            //这里需要注意越界的问题
            //向左边找
            if(y-1>=0&&!isSearch[x][y-1]) backTraceExist(board,word,count,x,y-1,row,col,isSearch);
            //向右边找
            if(y+1<col&&!isSearch[x][y+1]) backTraceExist(board,word,count,x,y+1,row,col,isSearch);
            //向上找
            if(x-1>=0&&!isSearch[x-1][y]) backTraceExist(board,word,count,x-1,y,row,col,isSearch);
            //向下找
            if(x+1<row&&!isSearch[x+1][y]) backTraceExist(board,word,count,x+1,y,row,col,isSearch);
            isSearch[x][y] = false;//回溯的思想，此趟搜索没有成功，就应该把此次的标记都释放掉！
        }
    }
};