剑指 Offer 12 矩阵中的路径

概述

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

https://leetcode.com/problems/word-search/

暴力遍历法

首先遍历整个矩阵，找出所有开始点，对每一个开始点，检查其周围是否有可选的下一个字母。

注意要为每一个开始点单独存储一个状态矩阵，用以记录对应的字母是否已被利用。

时间复杂度：O(m*n*l)，其中 l 为单词的长度。

回溯法 / 深度优先搜索

实际上和暴力遍历差不了多少，区别在于状态矩阵是用的 word 本身，避免了额外的内存消耗。

每次尝试后设置 board 中的字符为一个不可能的字符，试错后再设置回来，即所谓的回溯。

class Solution {
public:
    string word;
    bool exist(vector<vector<char>>& board, string word) {
        this->word = word;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (helper(board, 0, i, j)) return true;
            }
        }
        return false;
    }
    
    bool helper(vector<vector<char>>& board, int i, int r, int c) {
        if (r < 0 || c < 0 || r >= board.size() || c >= board[0].size()) return false;
        if (board[r][c] != word[i]) return false;
        board[r][c] = '.';  // set flag
        if (i == word.size() - 1) return true;
        if (helper(board, i + 1, r + 1, c) ||  helper(board, i + 1, r, c + 1) ||
            helper(board, i + 1, r - 1, c) ||  helper(board, i + 1, r, c - 1)) {
            return true;
        }
        board[r][c] = word[i];  // roll back
        return false;
    }
};

Links: sword-offer-12

未经允许，禁止转载，本文源站链接：https://iamazing.cn/