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 76 77
| class Solution { private: vector<vector<int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct TrieNode{ char value; vector<TrieNode*> children;
explicit TrieNode(char c):value(c){}; }; TrieNode* root = new TrieNode('#'); vector<string> result;
void dfs(vector<vector<char>>& board, int x, int y, string currentString, TrieNode* currentNode) { for(auto& childrenNode : currentNode->children) { if(board[x][y] == childrenNode->value) { currentString += board[x][y]; for(auto& nextNode : childrenNode->children) { if(nextNode->value == '#') { result.push_back(currentString); childrenNode->children.erase(find(childrenNode->children.begin(), childrenNode->children.end(), nextNode)); } } board[x][y] ^= 255; for(int i = 0; i < 4; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; if(dx < 0 || dx >= board.size() || dy < 0 || dy >= board[0].size()) { continue; } dfs(board, dx, dy, currentString, childrenNode); } board[x][y] ^= 255; } } } public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { set<string> wordsSet; for(const auto ¤tWord : words) { wordsSet.insert(currentWord); } for(auto currentWord : wordsSet) { if(currentWord.empty()) { result.emplace_back(""); continue; } currentWord += "#"; int index = 0; auto pre = root; while(currentWord[index]) { bool found = false; for(auto children : pre->children) { if(children->value == currentWord[index]) { found = true; pre = children; break; } } if(!found) { auto nextNode = new TrieNode(currentWord[index]); pre->children.push_back(nextNode); pre = nextNode; } index++; } } if(board.empty() || board[0].empty()) { return result; } for(int i = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++) { dfs(board, i, j, "", root); } } return result; } };
|