Skip to content

Latest commit

 

History

History
135 lines (106 loc) · 4.11 KB

of012.md

File metadata and controls

135 lines (106 loc) · 4.11 KB
description
剑指 Offer 06. 从尾到头打印链表

OF12.矩阵中的路径

题目描述

题目地址

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

示例 1：

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

题解

思路1 ： 递归回朔

递归遍历

算法流程：

  1. **复杂度分析：**循环遍历矩阵中每个元素，分别判断上线左右，但是走过的撸不能在走，所以只用看3个方向。
  2. 时间复杂度$$O(MN3^L)$$：其中遍其中M、N为矩阵的长宽，L为字符串的长度。
  3. 空间复杂度$$O(L)$$：

代码

{% tabs %} {% tab title="Go" %}

func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			//如果在数组中找得到第一个数，就执行下一步，否则返回false
			if dfs(board, i, j, word) {
				return true
			}
		}
	}
	return false
}
func dfs(board [][]byte, i, j int, word string) bool {
	//如果找到最后一个数，则返回true,搜索成功
	if len(word) == 0 {
		return true
	}
	//i,j的约束条件
	if i < 0 || j < 0 || i == len(board) || j == len(board[0]) {
		return false
	}

	//进入DFS深度优先搜索
	//先把正在遍历的该值重新赋值，如果在该值的周围都搜索不到目标字符，则再把该值还原
	//如果在数组中找到第一个字符，则进入下一个字符的查找
	if board[i][j] == word[0] {
		temp := board[i][j]
		board[i][j] = ' '
		//下面这个if语句，如果成功进入，说明找到该字符，然后进行下一个字符的搜索,直到所有的搜索都成功，
		//即k == len(word) - 1 的大小时，会返回true，进入该条件语句，然后返回函数true值。
		if dfs(board, i, j+1, word[1:]) ||
			dfs(board, i, j-1, word[1:]) ||
			dfs(board, i+1, j, word[1:]) ||
			dfs(board, i-1, j, word[1:]) {
			return true
		} else {
			//没有找到目标字符，还原之前重新赋值的board[i][j]
			board[i][j] = temp
		}
	}

	return false
}

{% endtab %}

{% tab title="Python" %}

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board
        self.directs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # 依次从每个坐标递归检查
        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.dfs(row, col, word):
                    return True
        # 默认返回 False
        return False

    def dfs(self, row, col, suffix):
        # 递归终止条件
        if len(suffix) == 0:
            return True
        # 进入回溯前，检查边界
        if row < 0 or row == self.ROWS or col < 0 or col == self.COLS or self.board[row][col] != suffix[0]:
            return False
        self.board[row][col] = '#'
        # 检查 4 个方向
        for rowOffset, colOffset in self.directs:
            if self.dfs(row + rowOffset, col + colOffset, suffix[1:]):
                return True
        self.board[row][col] = suffix[0]
        return False

{% endtab %} {% endtabs %}

总结

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm