C++怎么實現詞語搜索

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

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.

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

解法一：

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 數組，直接對 board 數組進行修改，將其遍歷過的位置改為井號，記得遞歸調用完后需要恢復之前的狀態，參見代碼如下：

解法二：

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;
    }
};

關于“C++怎么實現詞語搜索”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C++怎么實現詞語搜索”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。