# C++ 22ms (beat 100%) trie solution

• I think the keypoint is we record which words share the same trie node (using index of the words)

``````class Solution {
public:
struct trie {
vector<trie*> child;
vector<int> idx;
trie() {
child.resize(26, NULL);
}
};
void square_find(vector<string>& words, trie *root, vector<vector<string>> &res, int pos, vector<string> &ans) {
string key;
trie *cur = root;
int i;
for (i = 0; i < pos; i++) {
if (!cur->child[ans[i][pos] - 'a'])
break;
cur = cur->child[ans[i][pos] - 'a'];
}
if (i != pos)
return;

for(int  id : cur->idx) {
ans.push_back(words[id]);
if(pos + 1 == words[id].size())
res.push_back(ans);
else
square_find(words, root,res, pos + 1, ans);
ans.pop_back();
}
}
vector<vector<string>> wordSquares(vector<string>& words) {
trie *root = new trie();
vector<vector<string>> res;
vector<string> ans;
for(int j = 0; j < words.size(); j++) {
trie *cur = root;
string w = words[j];
root->idx.push_back(j);
for (int i = 0 ; i < w.size(); i++) {
if (!cur->child[w[i] - 'a'])
cur->child[w[i] - 'a'] = new trie();
cur = cur->child[w[i] - 'a'];
cur->idx.push_back(j);
}
}
square_find(words, root, res, 0, ans);
return res;
}
};
``````

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