79-word-search.md

79. Word Search - 单词搜索

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

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

示例:

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

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

---

题目标签：Array / Backtracking

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	20 ms	2.6 MB

static auto _ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

const int N = 1000;

class Solution {
public:
    int n, m;
    bool vt[N][N];
    bool res;
    
    void dfs(vector<vector<char>>& board, string& word, int x, int y, int p) {
        if (p == word.size() || res) {
            res = true;
            return;
        }

        int dx[] = {1, 0, -1, 0};
        int dy[] = {0, 1, 0, -1};
        for (int i=0; i<4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && word[p] == board[nx][ny] && !vt[nx][ny]) {
                vt[nx][ny] = true;
                dfs(board, word, nx, ny, p+1);
                vt[nx][ny] = false;
            }
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        if (!word.size()) { return true; }
        if (!board.size() || !board[0].size()) { return false; }
        
        n = (int)board.size();
        m = (int)board[0].size();
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j) {
                if (board[i][j] == word[0] && !res) {
                    vt[i][j] = true;
                    dfs(board, word, i, j, 1);
                    vt[i][j] = false;
                }
            }
        }
        return res;
    }
};