12. 矩阵中的路径

🟠   🔖  数组 字符串 回溯 矩阵  🔗 力扣

题目

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。 注意：寻找单词时 必须 按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

示例 1：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCCED"

输出：true

示例 2：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "SEE"

输出：true

示例 3：

输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCB"

输出：false

提示：

• m == grid.length
• n = grid[i].length
• 1 <= m, n <= 6
• 1 <= target.length <= 15
• grid 和 target 仅由大小写英文字母组成

注意

本题与 LeetCode 第 79 题 相同。

解题思路

1. 遍历整个二维字符网格，找到与单词的首字母匹配的位置。
2. 对于每一个匹配的位置，从这个位置出发进行深度优先搜索（DFS），尝试构建出给定的单词。
3. 在 DFS 的过程中，需要标记已经访问过的单元格，防止重复访问。
4. 如果在 DFS 的过程中成功构建出给定的单词，则返回true，否则返回false。

复杂度分析

• 时间复杂度: O(m*n*4^L)

  这个算法的时间复杂度主要由两部分组成：

  1. 对于每个可能的起始位置，都进行了一次 DFS 搜索，DFS 的时间复杂度为 O(4^L) ，其中 L 是给定单词的长度。
  2. 遍历整个二维字符网格，时间复杂度为 O(m*n)，其中 m 和 n 分别为网格的行数和列数。

  综合考虑，总的时间复杂度为 O(m*n*4^L) 。

• 空间复杂度: O(L)

  空间复杂度则主要由 DFS 的递归调用栈所占用的空间，最坏情况下为 O(L)。

代码

/**
 * @param {character[][]} grid
 * @param {string} target
 * @return {boolean}
 */
var wordPuzzle = function (grid, target) {
	const m = grid.length;
	const n = grid[0].length;

	const dp = (i, j, index) => {
		// 边界条件
		if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target[index]) {
			return false;
		}

		// 匹配成功的情况
		if (index == target.length - 1) {
			return true;
		}

		// 标记当前单元格已访问
		const temp = grid[i][j];
		grid[i][j] = '/';

		// 沿四个方向进行DFS
		const found =
			dp(i + 1, j, index + 1) ||
			dp(i - 1, j, index + 1) ||
			dp(i, j + 1, index + 1) ||
			dp(i, j - 1, index + 1);

		// 恢复当前单元格状态
		grid[i][j] = temp;
		return found;
	};

	// 遍历整个二维字符网格
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			// 如果找到匹配的首字母，开始DFS
			if (grid[i][j] == target[0] && dp(i, j, 0)) {
				return true;
			}
		}
	}
	// 没有找到匹配的情况
	return false;
};