Given a set of wordswithout duplicates, find all`word squares`you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence`["ball","area","lead","lady"]`forms a word square because each word reads the same both horizontally and vertically.

``````b a l l
a r e a
l e a d
l a d y
``````
##### Notice
• There are at least 1 and at most 1000 words.
• All words will have the exact same length.
• Word length is at least 1 and at most 5.
• Each word contains only lowercase English alphabet `a-z` .

Have you met this question in a real interview?

Yes

Example

``````Given a set ["area","lead","wall","lady","ball"]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Given a set ["abat","baba","atan","atal"]
return [["baba","abat","baba","atan"],["baba","abat","baba","atal"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
``````

class Solution {

public:

``````/\*\*

\* @param words a set of words without duplicates

\* @return all word squares

\*/

vector&lt;vector&lt;string&gt;&gt; wordSquares\(vector&lt;string&gt;& words\) {

if \(words.empty\(\)\) {

return squares;

}

initPrefix\(words\);

wordLen = words\[0\].size\(\);

search\(0\);

return squares;

}

bool checkPrefix\(int l, string nextWord\) {

for \(int j = l + 1; j &lt; wordLen; ++j\) {

string pre;

for \(int i = 0; i &lt; l; ++i\) {

pre += square\[i\]\[j\];

}

pre += nextWord\[j\];

if \(trieTree.FindByPrefix\(pre\).size\(\) == 0\) {

return false;

}

}

return true;

}

void search\(int l\) {

if \(l == wordLen\) {

squares.push\_back\(square\);

}

string pre = "";

for \(int i = 0; i &lt; l; ++i\) {

pre += square\[i\]\[l\];

}

vector&lt;string&gt; nextWords = trieTree.FindByPrefix\(pre\);

for \(string& nextWord : nextWords\) {

if \(!checkPrefix\(l, nextWord\)\) {

continue;

}

square.push\_back\(nextWord\);

search\(l + 1\);

square.pop\_back\(\);

}

}

void initPrefix\(vector&lt;string&gt;& words\) {

for \(string& word : words\) {

trieTree.insert\(word\);

}

}

vector&lt;vector&lt;string&gt;&gt; squares;

vector&lt;string&gt; square;

int wordLen;

class TrieNode {

public:

TrieNode \(\) {

}

vector&lt;string&gt; startWith;

unordered\_map&lt;char, TrieNode\*&gt; children;

};

class Trie {

public:

Trie\(\){

root = new TrieNode\(\);

};

void insert\(string s\) {

TrieNode\* node = root;

for \(int i = 0; i &lt; s.length\(\); ++i\) {

node-&gt;startWith.push\_back\(s\);

int ch = s\[i\] - 'a';

if \(!node-&gt;children.count\(ch\)\) {

node-&gt;children\[ch\] = new TrieNode\(\);

}

node = node-&gt;children\[ch\];

}

node-&gt;startWith.push\_back\(s\);

}

vector&lt;string&gt; FindByPrefix\(string prefix\) {

TrieNode\* node = root;

for \(int i = 0; i &lt; prefix.length\(\); ++i\) {

int ch = prefix\[i\] - 'a';

if \(!node-&gt;children.count\(ch\)\)

return {};

node = node-&gt;children\[ch\];

}

return node-&gt;startWith;

}

TrieNode\* root;

};

Trie trieTree;
``````

};