首页 剑指 Offer 12. 矩阵中的路径
文章
取消

剑指 Offer 12. 矩阵中的路径

题目描述

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

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

例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。

img

示例 1:

1
2
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

1
2
输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false

提示:

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

解题

每个位置都可能是单词的起点,因此需要双重循环遍历 board 中的每个元素,只要某个位置能够组成单词,就返回 true。

如何判断 i j 位置是否能移动组成单词 word 呢?

就判断当前 i j 是否和当前位置的 word 字符相等,相等就让 i j 向 4 个方向移动,递归执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:
    int rows, cols;
    bool backTrack(vector<vector<char>>& board, int i, int j, int cur, string& word) {
        if ( i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != word[cur] ) return false;
        if ( cur == word.size() - 1 ) return true;

        board[i][j] = '\0';
        bool res = backTrack(board, i + 1, j, cur + 1, word) || backTrack(board, i - 1, j, cur + 1, word) || backTrack(board, i, j + 1, cur + 1, word) || backTrack(board, i, j - 1, cur + 1, word);
        board[i][j] = word[cur];

        return res;
    } 
public:
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();

        for ( int i = 0; i < rows; i++ ) {
            for ( int j = 0; j < cols; j++ ) {
                if ( backTrack(board, i, j, 0, word) ) return true;
            }
        }

        return false;
    }
};

写在最后

感谢你在茫茫人海中找到我🕵🏼

🎉你是第 个读者

㊗️ 你平安喜乐,顺遂无忧!

希望你读完有所收获~

🥂🥂🥂

本文由作者按照 CC BY 4.0 进行授权

剑指 Offer 26. 树的子结构

剑指 Offer 13. 机器人的运动范围