題目：?
給定一個二維網(wǎng)格和一個單詞，找出該單詞是否存在于網(wǎng)格中。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母不允許被重復使用。

示例:

board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E'] ]給定 word = "ABCCED", 返回 true. 給定 word = "SEE", 返回 true. 給定 word = "ABCB", 返回 false.

?解題方法：遞歸回溯

type pair struct{ x, y int }var directions = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右func exist(board [][]byte, word string) bool {h, w := len(board), len(board[0])//初始化二維數(shù)組vis := make([][]bool, h)for i := range vis {vis[i] = make([]bool, w)}var check func(i, j, k int) boolcheck = func(i, j, k int) bool {if board[i][j] != word[k] { // 剪枝：當前字符不匹配return false}//k表示字符串對應的下標數(shù)即長度if k == len(word)-1 { // 單詞存在于網(wǎng)格中return true}//已訪問設置為truevis[i][j] = truedefer func() { vis[i][j] = false }() // 回溯時還原已訪問的單元格for _, dir := range directions {//重新確定下標并判斷下標的有效性和判斷下標是否訪問過if newI, newJ := i+dir.x, j+dir.y; 0 <= newI && newI < h && 0 <= newJ && newJ < w && !vis[newI][newJ] {if check(newI, newJ, k+1) {return true}}}return false}for i, row := range board {for j := range row {if check(i, j, 0) {return true}}}return false }

遞歸回溯的思想，先判斷單詞第一個字符的是否存在，然后上下左右進行遞歸查找，每個位上亦是如此。如果發(fā)現(xiàn)字符不相等就直接return相當于剪枝操作。遞歸要注意終止條件，當?shù)较聵诉_到與字符串長度相等時，則結束遞歸。

?

?

?

參考鏈接：https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/

總結

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

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