单词搜索

单词搜索(Word Search) ⭐️⭐️⭐️

LeetCode每日一题 2020.09.13

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中”相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

Example:

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

给定 word = "ABCCED" 返回 true
给定 word = "SEE" 返回 true
给定 word = "ABCB" 返回 false

note:
1. board 和 word 中只包含大写和小写英文字母.
2. 1 <= board.length <= 200
3. 1 <= board[i].length <= 200
4. 1 <= word.length <= 10^3

题目大意

按照题目大意需要在给定的board二维数组检索能够组成给定的word的一条路径

解题思路

比如单词 "ABCCED"。首先找到单词开头A，遍历矩阵，找到 A。
起点可能不止一个 $board(1,1)$ 和 $board(3,1)$ ，基于其中一个 A，利用DFS思想能否找出剩下的 “BCCED” 路径。
下级字符B有四个可选点: 当前A点的上、下、左、右。
逐个尝试每一种选择，去检索是否符合进而对下一个字符选点，又有四种选择，继续尝试检索。此处利用回溯的思想。
当发现某个选择四个方向均不符合，结束当前检索，回溯到上一层节点选择其他方向。
最终为ABCCED找到符合的节点路径 $board(1,1)\rightharpoonup board(1,2)\rightharpoonup board(1,3)\rightharpoonup board(2,3)\rightharpoonup board(3,3)\rightharpoonup board(3,2)$
关于判断元素是否使用过，我用了一个二维数组 mark 对使用过的元素做标记。

Solution

type pair struct{ x, y int }
// 定义上下左右四个行走的方向
var directions = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func exist(board [][]byte, word string) bool {
    var b_h = len(board)
    if b_h <= 0 {
        return false
    }
    var b_w = len(board[0])
    marked := make([][]bool, b_h)
    for i := range marked {
		marked[i] = make([]bool, b_w)
    }
    
	var search func(startX, startY, k int) bool
	search = func(startX, startY, k int) bool {
        // 当前字符不匹配
		if board[startX][startY] != word[k] {
			return false
        }
        // 检索完整个字串返回 true
		if k == len(word)-1 {
			return true
		}
        marked[startX][startY] = true
        // 四个方向均错误时回溯, defer恢复mark中对应的节点为未访问
		defer func() { marked[startX][startY] = false }() 
		for _, dir := range directions {
            // 需要判断节点在边界的情况, 防止越界
			if newX, newY := startX+dir.x, startY+dir.y; 0 <= newX && newX < b_h && 0 <= newY && newY < b_w && !marked[newX][newY] {
                // 递归查询
				if search(newX, newY, k+1) {
					return true
				}
			}
		}
		return false
    }
    // 按照word检索整个board
	for a, rows := range board {
		for b := range rows {
			if search(a, b, 0) {
				return true
			}
		}
	}
	return false
}