小米面试题：单词搜索

题目： 
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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) boolcheck = func(i, j, k int) bool {if board[i][j] != word[k] { // 剪枝：当前字符不匹配return false}//k表示字符串对应的下标数即长度if k == len(word)-1 { // 单词存在于网格中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 }

递归回溯的思想，先判断单词第一个字符的是否存在，然后上下左右进行递归查找，每个位上亦是如此。如果发现字符不相等就直接return相当于剪枝操作。递归要注意终止条件，当到下标达到与字符串长度相等时，则结束递归。

 

 

 

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

总结

以上是生活随笔为你收集整理的小米面试题：单词搜索的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。