leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0212.cpp (1639B)

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