该系列文章为本人刷leetcode的记录,主要旨在分享刷题的思路及算法解析(尽可能的一题多解),另方便自己日后查阅回顾。代码的实现语言是python和go。
想进大厂免不了刷题,一起加油吧，小伙伴们！
题目 offer 第12题 矩阵中的路径链接: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
题目内容给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8wmjixl6-1635428602322)(image-20211028084750801-16353820730801.png)]
示例 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
- board 和 word 仅由大小写英文字母组成
分析:这题是典型的回溯法;不断的试错直到找到答案，或者矩阵中不存在该字符串;
解法:DFS(深度优先搜索)+回溯;
具体实现过程:首先针对矩阵中的每一个元素都做起点开始全矩阵搜索是否存在该条路径，只要有任一条路径匹配就返回;
以矩阵第一个元素mat[0] [0] = A为例: 假如其和字符串首字母不匹配直接进行用下一字符mat[0] [1]=B 进行DFS搜索; 如果A匹配首字符那么,就向A的前后左右四个方向进行递归搜索与字符串下一字符是否匹配;且注意在每一次递归中使用过的(已匹配上的字符)要进行屏蔽,直到整个向下递归的过程全部结束后再将所有的所有匹配上的字符串进行一个个return还原成原矩阵中的字符(因为比如以mat[0] [0]=A为首的整个dfs搜索匹配过程不一定会成功,假如不成功就得开始以mat[0] [1] =B为首的进行匹配搜索, 所以得让上一次DFS过程中所有被屏蔽的字符进行还原,以顺利进行下一次搜索);
代码实现 pythondef exist(mat,words:str) -> bool:
if not mat: return False
#方法1:DFS递归;注意有个回溯的过程;
# def recur(i,j,k):
#
# #递归终止条件;以首字符A的DFS过程为例
# #搜索的元素越界;或者当前的元素与待匹配的字符不相等
# if not 0<= i < len(mat) or not (0<= j index: path = path[:index] #这里很精妙;保证了每次遍历添加的节点不会再被使用且当有多个节点被同时添加时;能保证其顺序
path.append((x, y))
#如果完整路径被找到了,即words每个元素都被按照排列顺序的遍历到了;那么返回true
if index == len(words)-1: return True
#向A元素的四个方向开始寻找下一元素是否与其字符串的下一字符相匹配;并且保证坐标没有越界;
#上
if 0<=x-1
go
package main
import (
"container/list"
"fmt"
"strconv"
)
func str_slice_contains(path []string, s string) bool{
if len(path)==0{return true}
for _,v := range path{
if v == s{return false}
}
return true
}
func exists(mat [][]byte, words string) bool{
if len(mat)==0{return false}
//方法1:使用DFS递归
//var recur func(i,j,k int) bool
//recur = func(i,j,k int) bool{
// //设置递归终止条件
// if i<0 || i >= len(mat) || j<0 || j>=len(mat[0]) || mat[i][j] != words[k]{return false}
// if k == len(words)-1 {return true}//这个必须放在上面的if后面;因为最后一次比较结束才可以算是全部比较完了;
//
//
// mat[i][j]=' '
//
// //开启四个方向下一次递归
// ret := recur(i-1,j,k+1) || recur(i+1,j,k+1) || recur(i,j-1,k+1) || recur(i,j+1,k+1)
//
// mat[i][j] = words[k]
//
// return ret
//}
//for i:=0; iindex{path = path[:index]}
str_i,str_j := strconv.Itoa(i),strconv.Itoa(j)
path = append(path,fmt.Sprintf("%s%s",str_i,str_j))//字符串拼接直接用+号也可以
//进行向A的四周寻找下一匹配字符
//向上
if 0<= i-1 && i-1
总结
注意go的迭代写法有bug;
当测试用例为：会超时;bug应该出在入栈和出栈那边;这种特殊情况对于go来说处理还是得做特殊考虑；python语言则可以直接迭代出来结果且不超时;
[["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"],
["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","b"]]
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa"
