Word Squares
Understanding the Problem
We need to build squares of words where the grid reads the same horizontally and vertically. If you lay out the words as rows of a matrix, then reading column k from top to bottom must give you the same string as row k.
The symmetry has a useful consequence. Once we place the first few rows, the characters already on the grid fix what the prefix of the next row must be. If row 0 is "wall" and row 1 is "area", then column 2 reads "le" so far (the third character of "wall" is 'l', the third character of "area" is 'e'). Whatever word we pick for row 2 must start with "le".
That prefix constraint is what makes the problem tractable. Instead of trying every combination of words and checking the result, we build the square row by row and let the prefix at each step narrow the candidates.
Key Constraints:
1 <= words.length <= 1000→ With up to 1000 words, the unpruned search space is far too large, so we need the prefix constraint to cut branches early.1 <= words[i].length <= 4→ Word length is at most 4, so the backtracking depth is at most 4 and the square is at most 4x4.- All words have the same length → The grid is always square, so there are no mismatched dimensions to handle.
Approach 1: Brute Force Backtracking
Intuition
Try every sequence of L words and check whether the resulting grid is a valid word square. Pick a word for row 0, then a word for row 1, and so on. After filling all L rows, verify the symmetry property: for every position (i, j), the character at (i, j) must equal the character at (j, i).
This is correct but wasteful. We build the entire square before discovering it is invalid, even when row 1 already breaks the symmetry.
Algorithm
- For each word in the list, place it as row 0 of the square.
- For each subsequent row, try every word in the list.
- After filling all L rows, check if the grid satisfies the word square property:
grid[i][j] == grid[j][i]for all i, j. - If valid, add this combination to the result.
- Backtrack and try the next word.
Visualization and Code
Loading animation...
- Time Complexity: O(N^L * L^2). We try N words for each of the L rows, giving N^L complete combinations, and validating each one costs O(L^2).
- Space Complexity: O(L), excluding the output. The recursion depth is L, and the current square holds L word references. The result list is not counted as auxiliary space.
Since we check validity only after the square is full, we waste effort on the many combinations that already fail at row 1 or 2. The next approach checks the prefix constraint before placing each row, so it never builds a row that cannot fit.
Approach 2: Backtracking with Prefix Map (HashMap)
Intuition
The symmetry constraint grid[i][j] == grid[j][i] lets us reject doomed branches before placing a row. Once the first few rows are fixed, the prefix of the next row is already determined.
Say we have placed rows 0 through r-1 and want to place row r. Column r must spell the same string as row r. The first r characters of column r are grid[0][r], grid[1][r], ..., grid[r-1][r], which we already know. So the word for row r must start with this prefix.
We precompute a hash map from every prefix to the list of words that start with it, which turns each prefix lookup into a single hash-map access during backtracking.
The prefix match is a necessary condition for any valid square: if a candidate word does not match the prefix, the symmetry property already fails, so skipping it discards nothing. The pruning is also strong. Without it, placing row 2 means trying all N words. With a 2-character prefix, only words matching both characters survive, which is roughly N/676 words for uniformly distributed letters.
Algorithm
- Build a hash map where each key is a prefix and each value is a list of words starting with that prefix.
- Start backtracking with an empty square.
- To place row
r, compute the required prefix: concatenategrid[0][r], grid[1][r], ..., grid[r-1][r]. - Look up this prefix in the hash map to get candidate words.
- For each candidate, add it to the square and recurse for the next row.
- When the square has L rows, add it to the result.
Visualization and Code
Loading animation...
- Time Complexity: O(N L + N 26^L). Building the prefix map takes O(N L). The backtracking explores at most N 26^L paths, though prefix pruning makes it much faster in practice.
- Space Complexity: O(N L + L^2). The prefix map stores O(N L) entries. The recursion stack and current square use O(L^2).
The hash map approach builds a prefix string and hashes it at every step. A trie removes that overhead: it walks the prefix one character at a time, with no string construction or hashing.
Approach 3: Backtracking with Trie (Optimal)
Intuition
The algorithm is the same prefix-pruned backtracking as Approach 2, with the prefix lookup moved into a trie. Each trie node stores the indices of all words that pass through it. To find the candidates for a prefix, we walk from the root following the prefix characters and read the indices at the node we land on. Building a string and hashing it at every backtracking step is replaced by following at most L child pointers.
The node reached by walking the prefix characters holds exactly the indices of words that begin with that prefix, which is the same candidate set the hash map returns. If a prefix character has no child, no word matches and we prune. Enforcing the prefix at every row guarantees grid[j][i] equals grid[i][j] for every already-placed row, so any completed square is valid.
Algorithm
- Build a trie from all words. At each trie node, store a list of indices of words whose prefix passes through that node.
- Start backtracking with an empty square.
- To place row
r, compute the required prefix by reading columnrfrom the already-placed rows. - Walk down the trie following the prefix characters. If any character is missing, prune.
- At the final trie node, iterate over the stored word indices as candidates.
- For each candidate, add it to the square and recurse for the next row.
- When the square has L rows, add it to the result.
Visualization and Code
Loading animation...
- Time Complexity: O(N L + N 26^L). Building the trie takes O(N * L). The backtracking explores N starting words, and at each level the branching factor depends on how many words match the prefix. In practice, prefix pruning reduces this dramatically.
- Space Complexity: O(N L + L^2). The trie has at most O(N L) nodes. The recursion stack and current square use O(L^2).