给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ [‘A‘,‘B‘,‘C‘,‘E‘], [‘S‘,‘F‘,‘C‘,‘S‘], [‘A‘,‘D‘,‘E‘,‘E‘] ]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
解题思路:
1,从字母表的任意一个位置开始,跟字符串的首字母比较,如果相等则继续;否则比较下一个位置
2,如果比较完所有位置,有一个能成功,就成功。
3,对于匹配算法,是典型的深度优先搜索。
A,字母表和单词如果相等,则递归比较下一个位置,用一个同等大小的table记录是否访问过路径,如果访问失败,函数返回前恢复记录
B,字母表的移动方向有上下左右四种,单词的移动方向有从左往右
C,匹配失败有以下3种情况
(1),超出字母表边界
(2),当前位置不匹配
(3) ,当前位置已经被访问了
func exist(board [][]byte, word string) bool { if word == "" { return true } visited := make([][]bool, len(board)) for i := 0; i < len(board); i++ { visited[i] = make([]bool, len(board[0])) } for i := 0; i < len(board); i++ { for j := 0; j < len(board[0]); j++ { if board[i][j] == word[0] && match(board, word, i, j, 0, visited) { return true } } } return false } func match(board [][]byte, word string, i, j, index int, visited [][]bool) bool { if index >= len(word) { return true } //fmt.Println(board, word, i, j, index, visited, i >= len(board), j >= len(board[0]), len(board[0])) if i < 0 || j < 0 || i >= len(board) || j >= len(board[0]) || board[i][j] != word[index] || visited[i][j] { return false } visited[i][j] = true if match(board, word, i+1, j, index+1, visited) || match(board, word, i-1, j, index+1, visited) || match(board, word, i, j+1, index+1, visited) || match(board, word, i, j-1, index+1, visited) { return true } visited[i][j] = false return false }
地址:https://leetcode-cn.com/problems/word-search/
原文:https://www.cnblogs.com/smallleiit/p/13125503.html