LeetCode 425 - Word Squares

Difficulty: 🔴 Hard
Topics: Array, String, Backtracking, Trie

Solution

Problem Understanding

The problem is asking us to generate all possible word squares from a given list of unique words. A word square is a square arrangement of words such that the word at row i is identical to the word at column i for every i. In other words, reading across the rows and down the columns produces the same set of strings.

The input is a list of strings words where all words are of the same length and consist only of lowercase letters. The output is a list of lists, where each inner list represents one valid word square. Words may appear multiple times in a square, even though the original list contains unique words.

Key constraints include:

words.length is up to 1000, so brute-force generating all permutations would be too slow.
words[i].length is up to 4, meaning each square is at most 4x4.
All words are unique, simplifying lookup and indexing.
Each word contains only lowercase letters.

Important edge cases include:

Very small word lists, e.g., a single word that forms a 1x1 square.
Words with overlapping prefixes, which may allow multiple valid squares.
Words of length 1, which trivially form squares with themselves.

Approaches

Brute Force

The brute-force approach generates all possible sequences of words of length n (where n is the length of each word) and checks whether each sequence forms a valid word square. For each candidate sequence, we compare characters row-wise and column-wise. If all positions match, the sequence is valid.

This method is correct because it considers every combination, ensuring no square is missed. However, it is too slow because for m words of length n, there are O(m^n) possible sequences. Even with small n, m^n grows quickly and is not feasible for m = 1000.

Optimal Approach

The key insight is that a valid word square is defined by its prefixes. For the current partially constructed square, the next word must match the column prefix formed by previous words. For example, if we have:

ball
area

The prefix for the next word in the 3rd row is "le" because it must match the first two letters of the 3rd column formed by the previous rows.

To efficiently find words with a given prefix, we can use a Trie (prefix tree) or a hash map of prefixes to words. We then perform backtracking, trying each candidate word that matches the required prefix, and recursively building the square until it reaches length n.

This reduces the search space drastically compared to the brute-force approach, as we only consider words that match the current prefix instead of all words.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m^n * n^2)	O(n)	Generates all sequences, checks each square
Optimal	O(n * m * 4^n)	O(m * n^2)	Uses prefix lookup + backtracking to prune invalid sequences

Algorithm Walkthrough

Compute all possible prefix-to-word mappings. For each word and for every possible prefix (from length 1 to n-1), store a list of words that start with that prefix. This allows O(1) prefix lookup during backtracking.
Initialize an empty list square that will store the current word square being built.
Define a recursive backtracking function:
If square contains n words, it is complete. Add a copy of square to the results and return.
Determine the prefix for the next word by taking the i-th character of each existing word, where i is the current depth.
Look up all candidate words that match this prefix using the prefix map.
For each candidate word, append it to square and recursively call the function.
After recursion, remove the word from square (backtracking).
Iterate over each word in the input list and start the backtracking process with that word as the first row.

Why it works:

The prefix property ensures that each word added to the square maintains the word-square invariant. By recursively exploring all candidates and backtracking when necessary, the algorithm explores all valid configurations without wasting time on impossible sequences.

Python Solution

from typing import List, Dict
from collections import defaultdict

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        if not words:
            return []
        
        n = len(words[0])
        prefix_map: Dict[str, List[str]] = defaultdict(list)
        
        # Build prefix map
        for word in words:
            for i in range(1, n):
                prefix_map[word[:i]].append(word)
        
        results: List[List[str]] = []
        
        def backtrack(square: List[str]):
            if len(square) == n:
                results.append(square[:])
                return
            
            # Build prefix for the next row
            prefix = ''.join(word[len(square)] for word in square)
            
            for candidate in prefix_map.get(prefix, []):
                square.append(candidate)
                backtrack(square)
                square.pop()
        
        for word in words:
            backtrack([word])
        
        return results

This implementation first constructs a prefix_map for fast lookup. The backtrack function builds each square incrementally, ensuring the next word matches the column prefix. Backtracking guarantees that all valid squares are explored efficiently.

Go Solution

package main

func wordSquares(words []string) [][]string {
    if len(words) == 0 {
        return nil
    }
    
    n := len(words[0])
    prefixMap := make(map[string][]string)
    
    // Build prefix map
    for _, word := range words {
        for i := 1; i < n; i++ {
            prefix := word[:i]
            prefixMap[prefix] = append(prefixMap[prefix], word)
        }
    }
    
    var results [][]string
    var square []string
    
    var backtrack func()
    backtrack = func() {
        if len(square) == n {
            tmp := make([]string, n)
            copy(tmp, square)
            results = append(results, tmp)
            return
        }
        
        prefix := ""
        for _, w := range square {
            prefix += string(w[len(square)])
        }
        
        for _, candidate := range prefixMap[prefix] {
            square = append(square, candidate)
            backtrack()
            square = square[:len(square)-1]
        }
    }
    
    for _, word := range words {
        square = []string{word}
        backtrack()
    }
    
    return results
}

Go-specific notes: slice copying is necessary when appending a complete square to avoid modifying it during recursion. Strings are immutable in Go, so building prefixes requires concatenation. Nil slices are handled automatically by appending.

Worked Examples

Example 1

Input: ["area","lead","wall","lady","ball"]

Build prefix map:

"a": ["area"]
"ar": ["area"]
"l": ["lead","lady"]
"le": ["lead"]
"w": ["wall"]
"wa": ["wall"]
"b": ["ball"]
"ba": ["ball"]

Start with "ball", square = ["ball"]
Prefix for 2nd row = "a" → candidates: ["area"]
Square = ["ball","area"]
Prefix for 3rd row = "le" → candidates: ["lead"]
Square = ["ball","area","lead"]
Prefix for 4th row = "lady" → candidate: ["lady"]
Square = ["ball","area","lead","lady"] → complete

Repeat starting with "wall" → produces second square.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m * 4^n)	Backtracking explores at most 4 candidates per level for n levels, repeated for each starting word.
Space	O(m * n^2)	Prefix map stores all prefixes, recursion stack stores at most n words per path.

Even though the worst case can be exponential in n, small n <= 4 keeps it feasible.

Test Cases

# Provided examples
assert Solution().wordSquares(["area","lead","wall","lady","ball"]) == [["ball","area","lead","lady"],["wall","area","lead","lady"]]
assert Solution().wordSquares(["abat","baba","atan","atal"]) == [["baba","abat","baba","atal"],["baba","abat","baba","atan"]]

# Edge cases
assert Solution().wordSquares(["a"]) == [["a"]]  # single word, single letter
assert Solution().wordSquares(["ab","ba"]) == [["ab","ba"],["ba","ab"]]  # 2x2 word square
assert Solution().wordSquares(["abc","bca","cab"]) == []  # no valid square
assert Solution().wordSquares([]) == []  # empty input

Test	Why
["area","lead","wall","lady","ball"]	Standard 4x4 case with multiple solutions
["abat","baba","atan","atal"]	4x4 with repeated words in square