Word Squares
Hard · Tries · Array · String · Backtracking · Trie
Problem
A sequence of strings forms a word square if, for every k, the k-th row and the k-th column read the same string. For example, the rows "bat", "are", "tea" form a word square because the columns also read "bat", "are", "tea".
You are given an array of distinct strings words, all of the same length. Return all word squares you can build from them, in any order. The same word may be used more than once within a square, and the number of rows equals the word length.
Examples
Input: words = ["bat","are","tea","cat"] Output: [["bat","are","tea"],["cat","are","tea"]]
Both "bat" and "cat" can start a square: the next rows are forced to begin with "a" and then "te".
Input: words = ["ab","ba"] Output: [["ab","ba"],["ba","ab"]]
Each word can start a square; the second row is forced by the first column.
Constraints
- 1 <= len(words) <= 1000
- 1 <= len(words[i]) <= 4
- All words[i] have the same length
- words[i] consists of lowercase English letters
- All words are distinct
Approaches
- Baseline: backtracking that scans every word — time O(S · n · L), space O(L)
Follow-up
A trie gives the same candidates as the prefix map with less memory (shared prefixes are stored once), at the price of walking down k nodes per row. The use cases count the squares instead of listing them, and forbid reusing a word within a square.
Related problems
Start free on Cariara · Coding problems · System design studio
