[数据结构与算法]offer 第12题 矩阵中的路径

前言

该系列文章为本人刷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过程中所有被屏蔽的字符进行还原,以顺利进行下一次搜索);

代码实现

python

def 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 <len(mat[0])) or mat[i][j]!=words[k]: return False
    #     #还有如果所有的字符都匹配上了递归也终止:
    #     if k == len(words)-1: return True
    #
    #
    #     #如果当前字符相匹配那么进行下一字符的匹配搜索;同时注意该次递归中相匹配的字符都要进行屏蔽
    #     mat[i][j]=" "
    #
    #     #找A的邻接字符(上下左右四个方向)是否与下一字符相匹配
    #     ret = recur(i+1,j,k+1) or recur(i-1,j,k+1) or recur(i,j+1,k+1) or recur(i,j-1,k+1)
    #
    #     #待整个以A为首的DFS搜索结束后将所有屏蔽的字符串依次return还原,以保障下一次DFS的顺利进行
    #     mat[i][j] = words[k]
    #     return ret
    #
    # #开启以矩阵中每个元素为首字符的DFS搜索
    # for i in range(len(mat)):
    #     for j in range(len(mat[0])):
    #        if recur(i,j,0): return True
    #
    #
    #
    # return False

    #方法2:有递归考虑能否用非递归的解法
    #首先,求出矩阵中与words首字符相等的所有元素的坐标;并沿着每一个进行全矩阵搜索是否存在路径;
    #搜索过程如下:比如有四个元素A、B、C、D与words首字符相等;
    #那么先将A入栈,之后将A出栈后,搜索A的四周元素有没有与words下一元素相等的,有的话入栈,并继续进行出栈操作,直到完整的路径都被找到就返回true;
    # (在入栈过程中必须保证已入栈过的元素不能再次入栈)
    # 如果第一次A出栈后没有,那就开始下一次大循环换成以B为首的元素,重复上述过程

    Wds0_index = []
    for i in range(len(mat)):
        for  j  in  range(len(mat[0])):
            if mat[i][j]==words[0]:  Wds0_index.append((i,j)) #python中支持向量添加

    stack = []
    index=0#k表示words的第几个字符

    #开始以所有words首字符相等的元素为起点开始进行寻找路径
    for eles in Wds0_index:
        #先将words的已被匹配的首字符入栈
        stack.append(eles)
        path = [] #path用于记录已入栈的元素路径


        while stack:
            #这题出栈的顺序要按照二叉树的深度优先遍历顺序,后进先出.这样保证每一个先进的节点能和其子节点对应上
            x,y,index =stack.pop()

            if len(path)> index: path = path[:index] #这里很精妙;保证了每次遍历添加的节点不会再被使用且当有多个节点被同时添加时;能保证其顺序

            path.append((x, y))

            #如果完整路径被找到了,即words每个元素都被按照排列顺序的遍历到了;那么返回true
            if index == len(words)-1: return True

            #向A元素的四个方向开始寻找下一元素是否与其字符串的下一字符相匹配;并且保证坐标没有越界;
            #上
            if 0<=x-1<len(mat) and mat[x-1][y]==words[index+1] and (x-1,y) not in path:
                stack.append((x-1,y,index+1))
            #下
            if 0<=x+1<len(mat) and mat[x+1][y]== words[index+1] and (x+1,y) not in path:
                stack.append((x+1,y,index+1))
            #左
            if 0<=y-1<len(mat[0]) and mat[x][y-1]==words[index+1] and (x,y-1) not in path:
                stack.append((x,y-1,index+1))
            #右
            if 0<= y+1<len(mat[0]) and mat[x][y+1]==words[index+1] and (x,y+1) not in path:
                stack.append((x,y+1,index+1))

    return False

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; i<len(mat); i++{
	//	for j:=0; j<len(mat[0]); j++{
	//		if recur(i,j,0){return true}
	//	}
	//
	//}
	//
	//
	//return false


	//方法2:非递归;遍历解法
	//有递归解法的时候一般都可以用遍历解法;

	Wds0 := make([][]int,0)
	//首先找到所有与字符串首字符相等的元素的位置
	for i:=0; i<len(mat); i++{
		for j:=0; j<len(mat[0]); j++{
			if mat[i][j] == words[0]{Wds0=append(Wds0,[]int{i,j})}
		}
	}

	if len(Wds0)==0{return false}

	//stack := make([][]int,0)
	//栈和队列的使用还是避免使用切片;否则每次出栈入栈都得调用整体的切片一次
	//使用双链表来模拟栈
	stack := list.New()


	for _,v:= range Wds0{
		path := make([]string,0)
		i,j := v[0],v[1]
		index :=0

		//将首字符A的坐标入栈
		stack.PushFront([]int{i,j,index})

		for stack.Len()!=0{
			//获取出栈元素的坐标
			node := stack.Remove(stack.Front()).([]int)

			i,j,index = node[0],node[1],node[2]

			if index==len(words)-1{return true}

			if len(path)>index{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<len(mat) && mat[i-1][j]==words[index+1] {
				if str_slice_contains(path,strconv.Itoa(i-1)+strconv.Itoa(j)){
					stack.PushFront([]int{i-1,j,index+1})
				}
			}

			//向下
			if 0<= i+1 && i+1<len(mat) && mat[i+1][j]==words[index+1]{
				if str_slice_contains(path,strconv.Itoa(i+1)+strconv.Itoa(j)){
					stack.PushFront([]int{i+1,j,index+1})
				}
			}

			//向左
			if 0<=j-1 && j-1<len(mat[0]) && mat[i][j-1]==words[index+1]{
				if str_slice_contains(path,strconv.Itoa(i)+strconv.Itoa(j-1)){
					stack.PushFront([]int{i,j-1,index+1})
				}
			}

			//向右
			if 0<=j+1 && j+1<len(mat[0]) && mat[i][j+1] == words[index+1]{
				if str_slice_contains(path,strconv.Itoa(i)+strconv.Itoa(j+1)){
					stack.PushFront([]int{i,j+1,index+1})
				}
			}
			
			

		}



	}

	return false

}

总结

注意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"