golang刷leetcode 技巧之如何解决矩阵中的路径问题

这篇文章将为大家详细讲解有关golang刷leetcode 技巧之如何解决矩阵中的路径问题,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false

提示:

  • 1 <= board.length <= 200

  • 1 <= board[i].length <= 200

解题思路

1,深度优先遍历

2,首字母不匹配可以剪枝

3,注意golang slice 数据地址一样,所以,需要clone 路径,否则会回溯失败

测试用例

[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]

"ABCESEEEFS"

[["a","b"]]

"ba"

[["a"]]

"a"

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]

"ABCCED"

代码实现

func exist(board [][]byte, word string) bool {   for i:=0;i<len(board);i++{       for j:=0;j<len(board[0]);j++{           if board[i][j]!=word[0]{               continue           }           mark:=getMark(board)           if dfs(board,mark,i,j,word){               return true           }           //fmt.Println(mark)       }   }   return false}
func dfs(board [][]byte,mark1 [][]int,i,j int,word string)bool{   if word=="" {       return true   }   if i<0 || i>=len(board) || j<0 || j>=len(board[0]) || board[i][j]!=word[0] || mark1[i][j]!=0{      return false   }
  if len(word)==1 && word[0]==board[i][j]{       return true   }    mark:=cloneMark(mark1)    mark[i][j]=1    return dfs(board,mark,i+1,j,word[1:]) ||    dfs(board,mark,i,j+1,word[1:]) ||    dfs(board,mark,i-1,j,word[1:])||    dfs(board,mark,i,j-1,word[1:])}
func getMark(board [][]byte)[][]int{    mark:=make([][]int,len(board))    for k:=0;k<len(board);k++{        mark[k]=make([]int,len(board[0]))    }    return mark}
func cloneMark(mark [][]int)[][]int{    mark1:=make([][]int,len(mark))    for i:=0;i<len(mark);i++{        mark1[i]=make([]int,len(mark[0]))        for j:=0;j<len(mark[0]);j++{            mark1[i][j]=mark[i][j]        }    }    return mark1}

关于“golang刷leetcode 技巧之如何解决矩阵中的路径问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。