快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(79.詞語搜索)

更新時(shí)間：2021年07月17日 14:50:25 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(79.詞語搜索),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 79. Word Search 詞語搜索

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
["ABCE"],
["SFCS"],
["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

這道題是典型的深度優(yōu)先遍歷 DFS 的應(yīng)用，原二維數(shù)組就像是一個(gè)迷宮，可以上下左右四個(gè)方向行走，我們以二維數(shù)組中每一個(gè)數(shù)都作為起點(diǎn)和給定字符串做匹配，我們還需要一個(gè)和原數(shù)組等大小的 visited 數(shù)組，是 bool 型的，用來記錄當(dāng)前位置是否已經(jīng)被訪問過，因?yàn)轭}目要求一個(gè) cell 只能被訪問一次。如果二維數(shù)組 board 的當(dāng)前字符和目標(biāo)字符串 word 對(duì)應(yīng)的字符相等，則對(duì)其上下左右四個(gè)鄰字符分別調(diào)用 DFS 的遞歸函數(shù)，只要有一個(gè)返回 true，那么就表示可以找到對(duì)應(yīng)的字符串，否則就不能找到，具體看代碼實(shí)現(xiàn)如下：

解法一：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = search(board, word, idx + 1, i - 1, j, visited) 
                 || search(board, word, idx + 1, i + 1, j, visited)
                 || search(board, word, idx + 1, i, j - 1, visited)
                 || search(board, word, idx + 1, i, j + 1, visited);
        visited[i][j] = false;
        return res;
    }
};

我們還可以不用 visited 數(shù)組，直接對(duì) board 數(shù)組進(jìn)行修改，將其遍歷過的位置改為井號(hào)，記得遞歸調(diào)用完后需要恢復(fù)之前的狀態(tài)，參見代碼如下：

解法二：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[idx]) return false;    
        char c = board[i][j];
        board[i][j] = '#';
        bool res = search(board, word, idx + 1, i - 1, j) 
                 || search(board, word, idx + 1, i + 1, j)
                 || search(board, word, idx + 1, i, j - 1)
                 || search(board, word, idx + 1, i, j + 1);
        board[i][j] = c;
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(79.詞語搜索)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)詞語搜索內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: