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