給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。

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

示例:

board =
[
? ['A','B','C','E'],
? ['S','F','C','S'],
? ['A','D','E','E']
]

給定 word = "ABCCED", 返回 true
給定 word = "SEE", 返回 true
給定 word = "ABCB", 返回 false
?

提示：

board 和 word 中只包含大寫和小寫英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

?

思路：回溯法，?一道搜索的題目，有點類似走迷宮，只不過按照給定單詞字母順序來尋找，遍歷board中每一個元素，判斷與word中的第一個字母是否相同，如果相同則在當前位置上去搜索上下左右相鄰的單元格的元素是否和當前字母的下一個字母相同，不在搜索范圍內(nèi)或者字母不同就返回false，當搜索的字母數(shù)等于word的長度時，也就表明在board找到了這個word。注意每次判斷一個字母要標記當前位置以搜索過，以防止字母重復利用。我選擇直接更改board元素，以便在后續(xù)的判斷中不會重復判斷此位置，在搜索結(jié)束后改回來就可以了。

class Solution { public:bool exist(vector<vector<char>>& board, string word) {int h = board.size();int w = board[0].size();for(int i=0;i<h;++i){for(int j=0;j<w;++j){if(core(board, word, 0, i, j, h, w)){return true;}}}return false;}bool core(vector<vector<char>>& board, string &word, int n, int x, int y, int h, int w){if(x < 0 || x > h-1 || y < 0 || y > w-1 || word[n] != board[x][y])return false;if(n == word.length()-1)return true;char temp = board[x][y];board[x][y] = 0;int flag = core(board, word, n+1, x+1, y, h, w)||core(board, word, n+1, x-1, y, h, w)||core(board, word, n+1, x, y+1, h, w)||core(board, word, n+1, x, y-1, h, w);board[x][y] = temp;return flag;} };

?

總結(jié)

以上是生活随笔為你收集整理的单词搜索—leetcode79的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。