LeetCode刷题：79. 单词搜索（golang版）

题目描述

示例图：

思路 1、深度优先递归当前格子的上下左右格子，看是否满足条件 2、递归终止条件，格子的行列坐标超出界限、格子已被使用过、格子字符不等于当前查找字符，返回false，或满足条件返回true 代码

package main

import "fmt"

func exist(board [][]byte, word string) bool {
          
   
	if len(board) == 0 {
          
   
		return false
	}
	//log标志位代表是否被访问过，row、col是行数和列数
	var (
		log  [6][6]bool
		row = len(board)
		col = len(board[0])
	)
	//遍历board,将board中等于word[0]的每个元素都作为一个入口，进行递归判断
	for i:=0; i<row; i++ {
          
   
		for j:=0; j<col; j++ {
          
   
			if board[i][j] == word[0] {
          
   
				if DFS(&board,&word,log,i,j,0) {
          
   
					return true
				}
			}
		}
	}
	return false
}
//rowI、colI分别代表board的行坐标列坐标，index 代表已匹配单词的长度
func DFS(board *[][]byte, word *string, log [6][6]bool, rowI int,colI int, index int) bool {
          
   
	//若index等于word的长度，则符合题意，返回true
	if index >= len(*word){
          
   
		return true
	}
	var (
		row = len(*board)
		col = len((*board)[0])
	)
	//递归终止条件，行里坐标超出界限或当前格子已被使用过，返回false
	if colI >= col || colI < 0 || rowI >= row || rowI < 0 || log[rowI][colI] == true {
          
   
		return false
	}
	//递归终止条件，不相等返回false
	if (*board)[rowI][colI] != (*word)[index] {
          
   
		return false
	}
	//将当前格子标记为已被使用过
	log[rowI][colI] = true
	//递归当前格子的上下左右格子
	return DFS(board,word,log,rowI-1,colI,index+1) || DFS(board,word,log,rowI+1,colI,index+1) || DFS(board,word,log,rowI,colI+1,index+1) || DFS(board,word,log,rowI,colI-1,index+1)
}

func main() {
          
   
	var tmp  = []byte{
          
   A,B,C,E}
	var t [][]byte
	t = append(t,tmp)
	tmp  = []byte{
          
   S,F,C,S}
	t = append(t,tmp)
	tmp  = []byte{
          
   A,D,E,E}
	t = append(t,tmp)
	
	res := exist(t,"ABCC")
	fmt.Println(res)
}