2026/04/18

[LeetCode] 212 Word Search II

LeetCode 79 的推廣版
從尋找一個字串升級到尋找多個字串
建一個Trie
只沿著prefix做dfs

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Trie {
public:
  static constexpr int NODESIZE = 26;
  bool isWord;
  string word;
  Trie* child[NODESIZE];

  Trie() {
    isWord = false;
    for (int i = 0; i < NODESIZE; i++)
      this->child[i] = nullptr;
  }

  void insert(string s) {
    Trie *node = this;
    for (auto &chr : s) {
        int idx = chr - 'a';
        if (!node->child[idx])
          node->child[idx] = new Trie();
        node = node->child[idx];
    }
    node->isWord = true;
    node->word = s;
  }
};

class Solution {
private:
  int dx[4] = {1, -1, 0, 0};
  int dy[4] = {0, 0, 1, -1};
  static constexpr int SIZE = 20;
  bool vis[SIZE][SIZE] = {0};
  int M, N;
  vector<string> ans;

  void dfs(int x, int y, Trie* trie, 
           vector<vector<char>>& board) {
    if (trie->isWord) {
      ans.push_back(trie->word);
      trie->isWord = false;
    }

    for (int i = 0; i < 4; i++) {
      if (x + dx[i] >= 0 && x + dx[i] < M &&
          y + dy[i] >= 0 && y + dy[i] < N && 
          !vis[x + dx[i]][y + dy[i]]) {
        vis[x + dx[i]][y + dy[i]] = true;
        int idx = board[x + dx[i]][y + dy[i]] - 'a';
        if (trie->child[idx]) 
          dfs(x + dx[i], y + dy[i], trie->child[idx], board);
        vis[x + dx[i]][y + dy[i]] = false;
      }
    }
  }

public:
  vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Trie* root = new Trie();
    for (string word : words)
      root->insert(word);

    M = board.size();
    N = board[0].size();
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) { 
        vis[i][j] = true;
        int idx = board[i][j] - 'a';
        if (root->child[idx]) 
          dfs(i, j, root->child[idx], board);
        vis[i][j] = false;
      }
    }
    return ans;
  }
};
Labels: