跳至主要內容

79. 单词搜索

79. 单词搜索open in new window

🟠   🔖  数组 字符串 回溯 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an m x n grid of characters board and a string word, return trueif word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

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

Output: true

Example 2:

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

Output: true

Example 3:

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

Output: false

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

题目大意

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路

  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[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
	const m = board.length;
	const n = board[0].length;

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

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

		// 标记当前单元格已访问
		const temp = board[i][j];
		board[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);

		// 恢复当前单元格状态
		board[i][j] = temp;
		return found;
	};
	// 遍历整个二维字符网格
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			// 如果找到匹配的首字母，开始DFS
			if (board[i][j] == word[0] && dp(i, j, 0)) {
				return true;
			}
		}
	}
	// 没有找到匹配的情况
	return false;
};

相关题目

题号标题题解标签难度
212单词搜索 IIopen in new window[✓]字典树 数组 字符串 2+
Copyright © 2024 2xiao