0212.cpp (1639B)
1 class Solution { 2 struct Node { 3 Node(){}; 4 Node *children[27] = {nullptr}; 5 bool &terminate = reinterpret_cast<bool &>(children[0]); 6 7 void insert(const string &s) { 8 Node *crnt = this; 9 for (const char c : s) { 10 const int idx = c & 0x1F; 11 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 12 crnt = crnt->children[idx]; 13 } 14 crnt->terminate = true; 15 } 16 }; 17 18 int n, m; 19 vector<string> res; 20 21 void dfs(vector<vector<char>> &board, Node *trie, int x, int y) { 22 const char c = board[x][y], idx = c & 0x1F; 23 if (c == '#' || !(trie = trie->children[idx])) return; 24 25 res.back().push_back(c); 26 if (trie->terminate) { 27 res.push_back(res.back()); 28 trie->terminate = false; 29 } 30 31 board[x][y] = '#'; 32 if (x > 0) dfs(board, trie, x - 1, y); 33 if (y > 0) dfs(board, trie, x, y - 1); 34 if (x < n) dfs(board, trie, x + 1, y); 35 if (y < m) dfs(board, trie, x, y + 1); 36 board[x][y] = c; 37 res.back().pop_back(); 38 } 39 40 public: 41 vector<string> findWords(vector<vector<char>> &board, const vector<string> &words) { 42 Node *trie = new Node(); 43 for (const string &word : words) 44 trie->insert(word); 45 46 n = board.size() - 1, m = board[0].size() - 1; 47 48 res.push_back(""); 49 for (int i = 0; i <= n; i++) { 50 for (int j = 0; j <= m; j++) { 51 dfs(board, trie, i, j); 52 } 53 } 54 res.pop_back(); 55 56 return res; 57 } 58 };