A word square matrix is naturally a symmetric matrix.
It means when we try the candidate words starting from the top row to the bottom row, the symmetric order will occur eventually, like in the above picture.
Therefore, we can interpret this situation as a constraint, and a constraint is nothing but a guide to pruning a solution tree.
As this question asks for all possible solutions to construct a word square and there occurs a constraint that helps us prune the tree, a kind of backtracking technique inevitably comes to mind.
In each insertion of the candidate words into the matrix, a prefix (which is the constraint at the same time) is built naturally.
Like in the picture:
When we insert ball into the matrix as the first candidate, we are obliged to insert a word starting with the prefixa into the second row.
After we insert the only suitable word "area", we are obliged to insert a word starting with the prefixle into the third row.
We could use a HashMap kind of data structure to store and retrieve the list of the words starting with the prefix needed.
We would use the prefix as a key, and the list of the words as the value.
But when we mention prefix and re(trie)ve, a Trie (prefix tree) data structure might be the perfect match.
The solution in the code is the fastest one on LeetCode. I just modularized and cleaned it to make it more readable.
Although the code is quite brilliant, there are some parts that disturb me.
For example, we need to fill an array with the same prefix tree to prune the root after each step. Sure, it helps to fasten the search on the tree, but there might be a leaner way about memory.
But for now, the solution is quite fine, according to me. When we turn back for this question to refactor it, we can think about making it leaner.
Resolves: https://github.com/spiralgo/algorithms/issues/220
A word square matrix is naturally a symmetric matrix. It means when we try the
candidatewords starting from the top row to the bottom row, the symmetric order will occur eventually, like in the above picture. Therefore, we can interpret this situation as aconstraint, and aconstraintis nothing but a guide to pruning a solution tree. As this question asks forall possible solutionsto construct a word square and there occurs aconstraintthat helps us prune the tree, a kind ofbacktracking techniqueinevitably comes to mind.In each insertion of the candidate words into the matrix, a
prefix(which is the constraint at the same time) is built naturally. Like in the picture:ballinto the matrix as the first candidate, we are obliged to insert a word starting with the prefixainto the second row.leinto the third row.We could use a HashMap kind of data structure to store and retrieve the list of the words starting with the prefix needed. We would use the prefix as a key, and the list of the words as the value.
But when we mention
prefixandre(trie)ve, a Trie (prefix tree) data structure might be the perfect match.The solution in the code is the fastest one on LeetCode. I just modularized and cleaned it to make it more readable. Although the code is quite brilliant, there are some parts that disturb me.
For example, we need to fill an array with the same prefix tree to prune the root after each step. Sure, it helps to fasten the search on the tree, but there might be a leaner way about memory.
But for now, the solution is quite fine, according to me. When we turn back for this question to refactor it, we can think about making it leaner.