# JS Solution

• The idea behind this problem is actually relatively simple. You would first build out a trie that would contain all the words.

You would then begin by setting up a for of loop for all the words, trying each of them as the top word of word squares.

Once you have the top word in a square, you check whether or not the character at index after the first letter forms a word, if it does, you add that word to the square.

Now you have two words in a square, and u look at whether the second from front character from each one of them is a prefix to a word in your trie. If so you add that word to the square as well.

You keep doing that and once you get to a point where the number of words in your square is equal to the length of the first word in the square you know you have a perfect word sqaure.

Why do you check the prefixes in the way that you do? Because of the mirror format of a word sqaure if you draw a diagonal through it from top left to bottom right.

``````class TrieNode {
constructor() {
this.children = {};
this.isWord = false;
}
}

class WordSquares {
constructor() {
this.root = new TrieNode();
}

wordSquares(words) {
let root = this.buildTrie(words);
let squares = [];

for (let word of words) {
let square = [];
square.push(word);
this.wordSquaresLong(root, word.length, square, squares);
}
return squares;
}

buildTrie(words) {
let root = this.root;

for (let word of words) {
let current = root;

for (let char of word) {
if (!current.children.hasOwnProperty(char)) {
current.children[char] = new TrieNode();
}
current = current.children[char];
}
current.isWord = true;
}
return root;
}

search(root, prefix) {
let current = root;
for (let char of prefix) {
if (!current.children.hasOwnProperty(char)) {
return null;
}
current = current.children[char];
}
return current;
}

wordSquaresLong(root, len, square, squares) {
if (square.length === len) {
squares.push(square.slice());
return;
}
let prefix = this.getPrefix(square, square.length);
let node = this.search(root, prefix);
if (!node) {
return;
}

let children = [];
this.getChildren(node, prefix, children);

for (let child of children) {
square.push(child);
this.wordSquaresLong(root, len, square, squares);
square.splice(square.length - 1, 1);
}
}

getPrefix(square, index) {
let prefix = '';
for (let i = 0; i < index; i++) {
prefix += square[i][index];
}
return prefix;
}

getChildren(node, str, children) {
if (node.isWord) {
children.push(str);
return;
}

for (let child of Object.keys(node.children)) {
this.getChildren(node.children[child], str + child, children);
}
}
}

/**
* @param {string[]} words
* @return {string[][]}
*/
var wordSquares = function(words) {
let wordSquaresClass = new WordSquares();
return wordSquaresClass.wordSquares(words);
};

wordSquares(['ball', 'lady', 'lead', 'area']);
``````

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