【leetcode】79. 单词搜索（word-search）（回溯）[中等]

链接

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

耗时

解题：50 min
题解：6 min

题意

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

思路

遍历二维网格，找 网格中字母 与 单词第一个字母相同 的位置，从这样的位置开始 dfs 找单词中剩下的字母，看能否通过 上下左右 寻找到全部。

时间复杂度： O ( n ∗ m ∗ 3 w o r d . s i z e ( ) ) O(n*m*3^{word.size()}) O(n∗m∗3word.size())

AC代码

class Solution {
private:
    vector<vector<char>> board;
    string word;
    bool ans = false;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n, m;
    bool vis[300][300];
public:
    void dfs(int x, int y, int pos) {
        if(pos == word.size()) {
            ans = true;
            return ;
        }
        vis[x][y] = true;
        for(int i = 0; i < 4; ++i) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if((nx >= 0 && nx < n) && (ny >= 0 && ny < m)) {
                if(vis[nx][ny]) continue;
                if(board[nx][ny] == word[pos]) {
                    dfs(nx, ny, pos+1);
                    if(ans) return ;
                }
            }
        }
        vis[x][y] = false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        this->board = board;
        this->word = word;
        n = board.size();
        m = board[0].size();
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(board[i][j] == word[0]) {
                    dfs(i, j, 1);
                    if(ans) return true;
                }
            }
        }
        return false;
    }
};