1
class Solution {
2
 public:
3
  vector<string> result;
4

5
  struct Trie {
6
    Trie *child[26];
7
    bool isEndOfWord;
8
    string str;
9

10
    Trie() {
11
      isEndOfWord = false;
12
      str = "";
13
      for (int i = 0; i < 26; i++) child[i] = NULL;
14
    }
15
  };
16

17
  Trie *root = new Trie();
18

19
  void insert(string &word) {
20
    Trie *curr = root;
21

22
    for (int i = 0; i < word.size(); i++) {
23
      int index = word[i] - 'a';
24

25
      if (!curr->child[index]) curr->child[index] = new Trie();
26

27
      curr = curr->child[index];
28
    }
29

30
    curr->isEndOfWord = true;
31
    curr->str = word;
32
  }
33

34
  void trieSearchDFS(vector<vector<char>> &board, Trie *curr, int i, int j, int row, int col) {
35
    if (i < 0 || i > row || j < 0 || j > col || board[i][j] == '@') return;
36

37
    // int index = board[i][j]-'a';
38
    curr = curr->child[board[i][j] - 'a'];
39

40
    if (curr == NULL) return;
41

42
    if (curr->isEndOfWord) {
43
      result.push_back(curr->str);
44
      curr->isEndOfWord = false;
45
    }
46

47
    char ch = board[i][j];
48
    board[i][j] = '@';
49

50
    if (i - 1 >= 0) trieSearchDFS(board, curr, i - 1, j, row, col);
51
    if (j + 1 < col) trieSearchDFS(board, curr, i, j + 1, row, col);
52
    if (i + 1 < row) trieSearchDFS(board, curr, i + 1, j, row, col);
53
    if (j - 1 >= 0) trieSearchDFS(board, curr, i, j - 1, row, col);
54

55
    board[i][j] = ch;
56
  }
57

58
  vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
59
    int row = board.size();
60
    int col = board[0].size();
61

62
    for (int i = 0; i < words.size(); i++) insert(words[i]);
63

64
    for (int i = 0; i < row; i++) {
65
      for (int j = 0; j < col; j++) {
66
        trieSearchDFS(board, root, i, j, row, col);
67
      }
68
    }
69
    return result;
70
  }
71
};