Untitled
unknown
c_cpp
a year ago
973 B
6
Indexable
struct TrieNode{ bool ends; int index; unordered_map<char, TrieNode*>child; TrieNode(): ends(false) {} }; void insert(string s, int index){ TrieNode* tmp = root; for(auto c: s){ if(tmp->child.find(c) == tmp->child.end()) tmp->child[c] = new TrieNode(); tmp = tmp->child[c]; } tmp->ends = true; tmp->index = index; return; } void query_suffix(string s, int index, vector<vector<int>> & ans){ TrieNode *tmp = root; for (auto c : s){ if (tmp->ends) ans.push_back({tmp->index, index}); tmp = tmp->child[c]; } return; } TrieNode* root = new TrieNode(); vector<vector<int>> problem4(vector<string> &word){ int n = word.size(); vector<vector<int>> ans; for(int i = 0; i < n; i++){ reverse(word[i].begin(), word[i].end()); insert(word[i], i); query_suffix(word[i], i, ans); } return ans; }
Editor is loading...
Leave a Comment