千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

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

发表于：2024-11-12 作者：千家信息网编辑
千家信息网最后更新 2024年11月12日，这篇文章将为大家详细讲解有关golang刷leetcode 技巧之如何解决矩阵中的路径问题，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。请设计一个函数，用来判断在一
千家信息网最后更新 2024年11月12日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       for j:=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        mark[k]=make([]int,len(board[0]))    }    return mark}
func cloneMark(mark [][]int)[][]int{    mark1:=make([][]int,len(mark))    for i:=0;i        mark1[i]=make([]int,len(mark[0]))        for j:=0;j            mark1[i][j]=mark[i][j]        }    }    return mark1}

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

很赞哦！
路径 矩阵 字符 字符串 格子 篇文章 一格 技巧 问题 再次 字母 更多 示例 输入 输出 不错 实用 一行 代码 内容 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 php做代理服务器 tc服务器架构 数据库怎样默认当前日期 泗洪购买网络技术诚信服务 数据库在tomcat哪里配置的 时序数据库市场 服务器主机运行怎么设置 实时数据库发展趋势 战地五怎么经营服务器 手机数据库高级工程师 万科邮箱接发服务器 csgo社区服务器安全吗 易信通信网络安全吗 dell服务器客服电话 身边的数据库系统有哪些 数据库理论与技术论文 我的世界服务器无限传送 南宁白话数据库 同步ntp服务器 数据库中字段类型文本 华为服务器允许切换时间 亚马逊 开源 数据库 万科邮箱接发服务器 用友系统 数据库 软件开发保护期 https协议怎么安装在服务器 国外服务器管理员 呼伦贝尔协创软件开发有限公司 嵌入式软件开发商窗户品牌 天天美剧软件开发

相关文章

0