comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9812.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84/README.md
面试题 12. 矩阵中的路径
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false
提示：
1 <= board.length <= 2001 <= board[i].length <= 200board和word仅由大小写英文字母组成
注意：本题与主站 79 题相同：https://leetcode.cn/problems/word-search/
解法
方法一：枚举 + DFS
我们可以枚举矩阵的每个位置 ( i , j ) (i, j) (i,j)，以该位置为起点，采用深度优先搜索的方法寻找字符串 word 的路径。如果找到了一条路径，即可返回 true，否则在枚举完所有的位置后，返回 false。
那么问题的转换为如何采用深度优先搜索的方法寻找字符串 word 的路径。我们可以设计一个函数 d f s ( i , j , k ) dfs(i, j, k) dfs(i,j,k)，表示从位置 ( i , j ) (i, j) (i,j) 开始，且当前将要匹配的字符为 word[k] 的情况下，是否能够找到字符串 word 的路径。如果能找到，返回 true，否则返回 false。
函数 d f s ( i , j , k ) dfs(i, j, k) dfs(i,j,k) 的执行流程如下：
- 如果当前字符
word[k]已经匹配到字符串word的末尾，说明已经找到了字符串word的路径，返回true。 - 如果当前位置 ( i , j ) (i, j) (i,j) 超出矩阵边界，或者当前位置的字符与
word[k]不同，说明当前位置不在字符串word的路径上，返回false。 - 否则，我们将当前位置的字符标记为已访问（防止重复搜索），然后分别向当前位置的上、下、左、右四个方向继续匹配字符
word[k + 1]，只要有一条路径能够匹配到字符串word的路径，就说明能够找到字符串word的路径，返回true。在回溯时，我们要将当前位置的字符还原为未访问过的状态。
时间复杂度 O ( m × n × 3 k ) O(m \times n \times 3^k) O(m×n×3k)，空间复杂度 O ( m × n ) O(m \times n) O(m×n)。其中 m m m 和 n n n 分别为矩阵的行数和列数，而 k k k 为字符串 word 的长度。我们需要枚举矩阵中的每个位置，然后对于每个位置，我们最多需要搜索三个方向。
a = pairwise(“abcdefg”) #获取连续重叠对
#a输出为"ab"bc"cd"de"ef"fg"
Python3
class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def dfs(i, j, k):if k == len(word):return Trueif i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:return Falseboard[i][j] = "" # 在递的过程中，标记已访问的方式，从而不会遍历到dirs = (-1, 0, 1, 0, -1)ans = any(dfs(i + a, j + b, k + 1) for a, b in pairwise(dirs))board[i][j] = word[k] #在归（回溯）的过程中，还原之前的状态return ansm, n = len(board), len(board[0])return any(dfs(i, j, 0) for i in range(m) for j in range(n))
Java
class Solution {private char[][] board;private String word;private int m;private int n;public boolean exist(char[][] board, String word) {m = board.length;n = board[0].length;this.board = board;this.word = word;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;}private boolean dfs(int i, int j, int k) {if (k == word.length()) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || word.charAt(k) != board[i][j]) {return false;}board[i][j] = ' ';int[] dirs = {-1, 0, 1, 0, -1};boolean ans = false;for (int l = 0; l < 4; ++l) {ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);}board[i][j] = word.charAt(k);return ans;}
}
C++
class Solution {
public:bool exist(vector<vector<char>>& board, string word) {int m = board.size(), n = board[0].size();int dirs[5] = {-1, 0, 1, 0, -1};function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {if (k == word.size()) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {return false;}board[i][j] = '.';bool ans = 0;for (int l = 0; l < 4; ++l) {ans |= dfs(i + dirs[l], j + dirs[l + 1], k + 1);}board[i][j] = word[k];return ans;};for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;}
};
Go
func exist(board [][]byte, word string) bool {m, n := len(board), len(board[0])var dfs func(i, j, k int) booldfs = func(i, j, k int) bool {if k == len(word) {return true}if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {return false}board[i][j] = ' 'dirs := []int{-1, 0, 1, 0, -1}ans := falsefor l := 0; l < 4; l++ {ans = ans || dfs(i+dirs[l], j+dirs[l+1], k+1)}board[i][j] = word[k]return ans}for i := 0; i < m; i++ {for j := 0; j < n; j++ {if dfs(i, j, 0) {return true}}}return false
}
TypeScript
function exist(board: string[][], word: string): boolean {const m = board.length;const n = board[0].length;const dfs = (i: number, j: number, k: number) => {if ((board[i] ?? [])[j] !== word[k]) {return false;}if (++k === word.length) {return true;}const temp = board[i][j];board[i][j] = ' ';if (dfs(i + 1, j, k) || dfs(i, j + 1, k) || dfs(i - 1, j, k) || dfs(i, j - 1, k)) {return true;}board[i][j] = temp;return false;};for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (dfs(i, j, 0)) {return true;}}}return false;
}
Rust
impl Solution {fn dfs(board: &mut Vec<Vec<char>>,chars: &Vec<char>,i: usize,j: usize,mut k: usize,) -> bool {if board[i][j] != chars[k] {return false;}k += 1;if k == chars.len() {return true;}let temp = board[i][j];board[i][j] = ' ';if (i != 0 && Self::dfs(board, chars, i - 1, j, k))|| (j != 0 && Self::dfs(board, chars, i, j - 1, k))|| (i != board.len() - 1 && Self::dfs(board, chars, i + 1, j, k))|| (j != board[0].len() - 1 && Self::dfs(board, chars, i, j + 1, k)){return true;}board[i][j] = temp;false}pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {let m = board.len();let n = board[0].len();let chars = word.chars().collect::<Vec<char>>();for i in 0..m {for j in 0..n {if Self::dfs(&mut board, &chars, i, j, 0) {return true;}}}false}
}
JavaScript
/*** @param {character[][]} board* @param {string} word* @return {boolean}*/
var exist = function (board, word) {const m = board.length;const n = board[0].length;const dirs = [-1, 0, 1, 0, -1];const dfs = (i, j, k) => {if (k == word.length) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {return false;}board[i][j] = ' ';let ans = false;for (let l = 0; l < 4; ++l) {ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);}board[i][j] = word[k];return ans;};for (let i = 0; i < m; ++i) {for (let j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;
};
C#
public class Solution {private char[][] board;private string word;private int m;private int n;public bool Exist(char[][] board, string word) {m = board.Length;n = board[0].Length;this.board = board;this.word = word;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (dfs(i, j, 0)) {return true;}}}return false;}private bool dfs(int i, int j, int k) {if (k == word.Length) {return true;}if (i < 0 || i >= m || j < 0 || j >= n || word[k] != board[i][j]) {return false;}board[i][j] = ' ';int[] dirs = {-1, 0, 1, 0, -1};bool ans = false;for (int l = 0; l < 4; ++l) {ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);}board[i][j] = word[k];return ans;}
}
Swift
class Solution {private var board: [[Character]]private var word: Stringprivate var m: Intprivate var n: Intinit() {self.board = []self.word = ""self.m = 0self.n = 0}func exist(_ board: [[Character]], _ word: String) -> Bool {self.board = boardself.word = wordm = board.countn = board[0].countfor i in 0..<m {for j in 0..<n {if dfs(i, j, 0) {return true}}}return false}private func dfs(_ i: Int, _ j: Int, _ k: Int) -> Bool {if k == word.count {return true}if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[word.index(word.startIndex, offsetBy: k)] {return false}let temp = board[i][j]board[i][j] = " "let dirs = [-1, 0, 1, 0, -1]var ans = falsefor l in 0..<4 {let ni = i + dirs[l]let nj = j + dirs[l + 1]if dfs(ni, nj, k + 1) {ans = truebreak}}board[i][j] = tempreturn ans}
}
