小米麵試題：單詞搜尋

題目： 
給定一個二維網格和一個單詞，找出該單詞是否存在於網格中。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中「相鄰」單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

範例:

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])

	//初始化二維陣列
	vis := make([][]bool, h)
	for i := range vis {
		vis[i] = make([]bool, w)
	}

	var check func(i, j, k int) bool
	check = func(i, j, k int) bool {
		if board[i][j] != word[k] { // 剪枝：當前字元不匹配
			return false
		}

		//k表示字串對應的下標數即長度
		if k == len(word)-1 { // 單詞存在於網格中
			return true
		}

		//已存取設定為true
		vis[i][j] = true
		defer 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
}

遞迴回溯的思想，先判斷單詞第一個字元的是否存在，然後上下左右進行遞迴查詢，每個位上亦是如此。如果發現字元不相等就直接return相當於剪枝操作。遞迴要注意終止條件，當到下標達到與字串長度相等時，則結束遞迴。

 

 

 

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