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

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

這篇文章主要介紹了C++實現(xiàn)LeetCode(79.詞語搜索),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(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 的應用，原二維數(shù)組就像是一個迷宮，可以上下左右四個方向行走，我們以二維數(shù)組中每一個數(shù)都作為起點和給定字符串做匹配，我們還需要一個和原數(shù)組等大小的 visited 數(shù)組，是 bool 型的，用來記錄當前位置是否已經(jīng)被訪問過，因為題目要求一個 cell 只能被訪問一次。如果二維數(shù)組 board 的當前字符和目標字符串 word 對應的字符相等，則對其上下左右四個鄰字符分別調(diào)用 DFS 的遞歸函數(shù)，只要有一個返回 true，那么就表示可以找到對應的字符串，否則就不能找到，具體看代碼實現(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ù)組，直接對 board 數(shù)組進行修改，將其遍歷過的位置改為井號，記得遞歸調(diào)用完后需要恢復之前的狀態(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++實現(xiàn)LeetCode(79.詞語搜索)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)詞語搜索內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: