hardTriesPure DSA~40 min
Build All Word Squares
A crossword tool arranges equal-length words into a square grid that reads the same across rows and down columns. Generate every such word square from a given vocabulary.
Problem
Given a list of unique words all of the same length, return all word squares you can build. A sequence of words forms a word square if, for every k, the k-th row equals the k-th column. The same word may be reused. Return all squares in any order.
Input
A list words of unique equal-length lowercase strings.
Output
A list of word squares, each a list of words.
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 5; all words share the same length.
Examples
Example 1
Input
words = ["area","lead","wall","lady","ball"]
Output
[["ball","area","lead","lady"],["wall","area","lead","lady"]]
Both squares read identically across rows and down columns.
Example 2
Input
words = ["abat","baba","atan","atal"]
Output
[["baba","abat","baba","atal"],["baba","abat","baba","atan"]]
Two valid squares are formed.