DSA problem
Word Squares
Given an array of unique strings words, return all the word squares you can build from words. The same word from words can be used multiple times. You can return the answer in any order.
A sequence of strings forms a valid word square if the k-th row and column read the same string, for all 0 <= k < max(numRows, numCols). For example, the sequence ["ball","area","lead","lady"] forms a word square because each row reads the same as the corresponding column.
The brute-force approach picks any word for the first row, then for each subsequent row scans the entire dictionary looking for words that satisfy the symmetric constraint. With N words of length L that costs O(N^L) in the worst case — completely impractical.
The optimal approach uses a Trie indexed by every prefix of every word: each Trie node stores the list of words that pass through it. To choose the k-th row of a partial square, we compute the required prefix (the characters in column k from already-placed rows) and ask the Trie in O(L) for every word that begins with it. Backtracking then becomes very tight: only viable candidates are tried at each level, slashing the search space dramatically.
Examples
words = ["area","lead","wall","lady","ball"][["ball","area","lead","lady"],["wall","area","lead","lady"]]words = ["abat","baba","atan","atal"][["baba","abat","baba","atal"],["baba","abat","baba","atan"]]words = ["a"][["a"]]Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 4
- All words[i] have the same length.
- words[i] consists of only lowercase English letters.
- All words[i] are unique.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.