【面试经典 150 | 回溯】单词搜索

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：回溯
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字符串】【回溯】

题目来源

79. 单词搜索

解题思路

方法一：回溯

思路

从每一个格子点开始搜索，利用回溯思想枚举所有字符串。在回溯中需要注意几个要点：

明确返回条件：
- 超出矩阵范围，直接 return；
- 格子点已经访问过，格点字符不是当前要找的字符，直接 retrun；
明确最终结束条件：已经到达 word 最后一个字符的洗标位置，更新 bool 值 find = true
从当前格点向上下左右四个方向进行搜索，继续调用回溯函数 backtrack，最后记得恢复现场（可能不走当前的格点）.

代码

class Solution {
private:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

	void backtrack(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, bool& find, int i, int j, int pos) {
		// 是否超出矩阵范围
		if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
			return;

		if (visited[i][j] || find || board[i][j] != word[pos])
			return;

		if (pos == word.size() - 1) {
			find = true;
			return;
		}
		visited[i][j] = true;
        for (int k = 0; k < 4; ++k) {
            int nx = i + dirs[k][0];
            int ny = j + dirs[k][1];
            backtrack(board, visited, word, find, nx, ny, pos + 1);
        }
        // 恢复现场
		visited[i][j] = false;
	}

public:
	bool exist(vector<vector<char>>& board, string word) {
		int m = board.size(), n = board[0].size();
		vector<vector<bool>> visited(m, vector<bool>(n, false));
		bool find = false;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
                backtrack(board, visited, word, find, i, j , 0);
            }				
		}
		return find;
	}
};

复杂度分析

时间复杂度：见分析.

空间复杂度： $O (mn)$ 。 $m$ 和 $n$ 分别为网格的行数和列数。我们额外开辟了 $O (mn)$ 的 visited 数组，同时栈的深度最大为 $O (min (L, mn))$ ， $L$ 为字符串 word 的长度。