# Trie Solution O(N*M*logM) time, O(N*M) space (more space efficient than hashtable)

• Using Trie data structure:

• O(NMlogM) time

• O(N*M) space, but typically more space efficient when there are many strings with overlapping prefixes (after being sorted)

class Node {
private:
int idx;
vector<Node*> child;
public:
Node() {
idx = -1;
for (int i = 0; i < 26; i++) {
child.push_back(NULL);
}
}
~Node() {
for (int i = 0; i < 26; i++) {
delete child[i];
}
}
void createChild(int id) {
child[id] = new Node();
}
Node* getChild(int id) {
return child[id];
}
int getIdx() {
return idx;
}
void setIdx(int newIdx) {
idx = newIdx;
}
};

class Trie {
private:
Node* _root;
int cnt;
public:
Trie() {
cnt = 0;
_root = new Node();
}
~Trie() {
delete _root;
}
int insert(string &str) {
int len = str.length();
Node* curr = _root;
for (int i = 0; i < len; i++) {
if (curr->getChild(str[i] - 'a') == NULL) {
curr->createChild(str[i] - 'a');
}
curr = curr->getChild(str[i] - 'a');
if (i == len - 1) {
if (curr->getIdx() == -1)
curr->setIdx(cnt++);
return curr->getIdx();
}
}
if (len == 0) {
if (_root->getIdx() == -1)
_root->setIdx(cnt++);
return _root->getIdx();
}
}
};

class Solution {
vector<string> ans;
vector<pair<int, int> > pairs;
public:
vector<string> anagrams(vector<string> &strs) {
Trie *trie = new Trie();
int cnt[strs.size()];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < strs.size(); i++) {
string sorted_strs = strs[i];
sort(sorted_strs.begin(), sorted_strs.end());
int idx = trie->insert(sorted_strs);
pairs.push_back({i, idx});
cnt[idx]++;
}
sort(pairs.begin(), pairs.end(), [](pair<int, int> a, pair<int, int> b){
return a.second < b.second;
});
for (int i = 0; i < strs.size(); i++) {
if (cnt[pairs[i].second] <= 1) continue;
ans.push_back(strs[pairs[i].first]);
}
delete trie;
return ans;
}
};

• Good practice for large input. (Obviously the OJ just use small inputs for every test case.) I must find a dictionary to try it.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.