題目描述：

給定一個(gè)?m x n?二維字符網(wǎng)格?board?和一個(gè)字符串單詞?word?。如果?word?存在于網(wǎng)格中，返回?true?；否則，返回?false?。

單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board?和?word?僅由大小寫(xiě)英文字母組成

進(jìn)階：你可以使用搜索剪枝的技術(shù)來(lái)優(yōu)化解決方案，使其在?board?更大的情況下可以更快解決問(wèn)題？

通過(guò)次數(shù)

462.9K

提交次數(shù)

997.8K

通過(guò)率

46.4%

思路和題解：

回溯和剪枝，設(shè)置一個(gè)函數(shù)check(i,j,k)判斷從網(wǎng)格的下標(biāo)[i][j]位置出發(fā)，能不能搜索到單詞word[k]...word[wordSize-1]（即word中下標(biāo)k開(kāi)始的后綴字符串）。判斷所有的check(i,j,0)，只要有一個(gè)為真即為真，否則為假。

對(duì)于check函數(shù)，如果board[i][j]!=word[k]，return false；如果board[i][j]!=word[k]&&k==wordSize-1，return true；否則就判斷相鄰的四個(gè)位置能不能搜到word[k+1]...word[wordSize-1]。

要注意的是，check函數(shù)中包含了多次遞歸調(diào)用，如果是c++的話，參數(shù)寫(xiě)成傳引用，這樣比值傳遞運(yùn)行速度快，能過(guò)。值傳遞的話我試過(guò)過(guò)不了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-734407.html

i代碼：

class Solution {
public:
    //往右，左，下，上四個(gè)方向走時(shí)行下標(biāo)的變化和列下標(biāo)的變化
    int directions[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    bool check(vector<vector<char>> &board,int m,int n,vector<vector<int>> &visited,int i,int j,string word,int wordSize,int k)
    {
        if(board[i][j]!=word[k])
            return false;
        else if(k==wordSize-1)
            return true;
        visited[i][j]=1;
        for(int direc=0;direc<4;direc++)
        {//依次往四個(gè)方向走
            int newi=i+directions[direc][0],newj=j+directions[direc][1];
            if(newi>=0&&newi<m&&newj>=0&&newj<n&&visited[newi][newj]==0)
            {
                bool flag=check(board,m,n,visited,newi,newj,word,wordSize,k+1);
                if(flag)
                {
                    return true;
                }
            }
        }
        visited[i][j]=0;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size();
        int n=board[0].size();
        vector<vector<int>> visited(m,vector<int>(n,0));
        int wordSize=word.size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                bool flag=check(board,m,n,visited,i,j,word,wordSize,0);
                if(flag)
                    return true;
            }
        }
        return false;
    }
};

到了這里，關(guān)于力扣每日一題79：?jiǎn)卧~搜索的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！