Word Squares II - Solution & Explanation

Problem Overview: You are given a list of words where each word has the same length. The task is to construct all possible word squares. A word square is a sequence of words such that the kth row and kth column read the same string. For example, the first word defines the first column, the second word must match the second column prefix, and so on.

Approach 1: Brute Force Enumeration (O(N! * L^2) time, O(L) space)

The naive idea is to try every possible ordering of words and check whether they form a valid square. Generate permutations using recursion or iterative enumeration, then validate the grid by comparing characters at grid[i][j] and grid[j][i]. Validation takes O(L^2) for word length L. This approach quickly becomes infeasible because permutations grow factorially with the number of words. It is mainly useful for understanding the structural constraint of word squares.

Approach 2: Backtracking with Prefix Hash Map (O(N * L^2 * B) time, O(N * L) space)

A more practical approach builds the square row by row using backtracking. When placing the kth word, the prefix formed by characters square[0][k], square[1][k], ..., square[k-1][k] must match the start of the candidate word. Precompute a prefix lookup table using a hash map where each prefix maps to all words that start with it. During recursion, compute the required prefix and fetch valid candidates in constant time. This prunes most invalid branches early, making the search manageable.

The algorithm iterates through each word as a starting row, then recursively fills the next rows while maintaining the prefix constraint. The prefix map is built by iterating through every word and storing prefixes of length 1..L. The recursion depth is at most L, and each step narrows candidates using prefix filtering. This combines string prefix matching with array style indexing for column validation.

Approach 3: Backtracking with Trie Prefix Search (O(N * L^2 * B) time, O(N * L) space)

Instead of a hash map, store all words in a Trie. Each Trie node tracks the indices of words that share the prefix represented by that node. While building the square, traverse the Trie using the required prefix and immediately retrieve candidate words. This reduces repeated prefix scans and keeps lookup efficient even when the dictionary is large.

Recommended for interviews: Backtracking with prefix lookup (hash map or Trie) is the expected solution. Interviewers want to see that you identify the prefix constraint and prune the search tree early. Starting with the brute-force permutation idea shows you understand the problem structure, but switching to prefix-guided backtracking demonstrates algorithmic optimization and practical search design.