C++怎么實現(xiàn)詞語搜索

這篇文章主要介紹了C++怎么實現(xiàn)詞語搜索的相關(guān)知識，內(nèi)容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++怎么實現(xiàn)詞語搜索文章都會有所收獲，下面我們一起來看看吧。

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ù)組就像是一個迷宮，可以上下左右四個方向行走，我們以二維數(shù)組中每一個數(shù)都作為起點和給定字符串做匹配，我們還需要一個和原數(shù)組等大小的 visited 數(shù)組，是 bool 型的，用來記錄當前位置是否已經(jīng)被訪問過，因為題目要求一個 cell 只能被訪問一次。如果二維數(shù)組 board 的當前字符和目標字符串 word 對應(yīng)的字符相等，則對其上下左右四個鄰字符分別調(diào)用 DFS 的遞歸函數(shù)，只要有一個返回 true，那么就表示可以找到對應(yīng)的字符串，否則就不能找到，具體看代碼實現(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)詞語搜索”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“C++怎么實現(xiàn)詞語搜索”知識都有一定的了解，大家如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道。