# Fully commented C++ solution using a Trie, inspired by @StefanPochmann

• class Solution {
public:

vector<string> W;
vector<vector<string> > Squares;
vector<string> Square;

struct TrieNode
{
vector<string> Words;
vector<TrieNode*> Nodes;

TrieNode()
:
Nodes(26,NULL)
{
}

} *Root = new TrieNode;

//
// Given the Root of the Trie add the string Str
// character by Character.
// For each node we visit on our way, we store the
// entire string in that node.
// this will allow us to access it quickly when
// we search for prefixes of this word
//

void AddWord(TrieNode *R, const string &Str)
{
if(Str.empty())
{
return;
}

R->Words.push_back(Str);

for(auto &c : Str)
{
if(R->Nodes[c - 'a'] == NULL)
{
R->Nodes[c - 'a'] = new TrieNode;
}

R = R->Nodes[c - 'a'];
R->Words.push_back(Str);
}
}

//
// Return all words that correspond to the prefix
// Str
//
vector<string> FindAll(TrieNode *R, const string &Str)
{
if(Str.empty())
{
return R->Words;
}

if(R == NULL || R->Nodes[Str[0] - 'a'] == NULL)
{
return vector<string>();
}

return FindAll(R->Nodes[Str[0] - 'a'],Str.substr(1));
}

//
// The main recursive function
// receives an index i which indicates
// the row in the square to be filled
//
void FillSquares(int i)
{
//
// when i is equal to the maximum number
// of rows in the square (size of a word)
// insert the Square into the vector<> Squares
//

if(i == W[0].size())
{
if(Square.size() == W[0].size())
{
Squares.push_back(Square);
}

return;
}

//
// The prefix is based on the the i'th column of the square
// We need to only take the k < i letters from this column
//

string Prefix;

for(int k = 0; k < i; ++k)
{
Prefix.push_back(Square[k][i]);
}

//
// FindAll will return all words that correspond
// to this prefix, and will try them all
//

for(auto &w : FindAll(Root,Prefix))
{
Square.push_back(w);
FillSquares(i + 1);
Square.pop_back();
}
}

vector<vector<string> > wordSquares(vector<string>& words)
{
W = words;

for(auto &w : words)
{