题目描述

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

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

样例

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

算法1

(DFS) $O(m * n * 3 ^{len(word)})$

搜索方案，DFS。

时间复杂度

每一步有三个方向可选，最多走$len(word)$步，所以每次搜索约为$O(3^{len(word)})$；
最坏情况下搜$O(mn)$次。

参考文献

C++ 代码

class Solution {
private:
    int m, n;
    vector<int> dr = {1, 0, -1, 0}, dc = {0, 1, 0, -1};
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty() || word.empty()) return false;
        m = board.size(); n = board[0].size();
        if (word.size() > m * n) return false;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false; 
    }

    bool dfs(vector<vector<char>> &board, int r, int c, const string &word, int idx){
        char tmp = board[r][c];
        if (tmp != word[idx]) return false;
        if (idx == word.size() - 1) return true;
        board[r][c] = '*';

        for (int k = 0; k < 4; ++k){
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] != '*'){
                if (dfs(board, nr, nc, word, idx + 1)) return true;
            }
        }
        board[r][c] = tmp;
        return false;
    }
};