Word Squares

Word Squares

What is this problem about?

A "Word Square" is a sequence of words such that the k-th row and k-th column are the same string. For example, if the first word is AREA, the first column must also be A, R, E, A. Given a list of words of the same length, you need to find all possible word squares that can be formed using those words.

Why is this asked in interviews?

Google loves this problem because it’s a pure test of Backtracking and Prefix Search efficiency. It requires you to realize that choosing the first i words in the square completely determines the required prefix for the (i+1)-th word. This observation is the key to solving the problem efficiently.

Algorithmic pattern used

The pattern is Backtracking with a Trie.

1. Build a Trie containing all words, where each node also stores a list of all words that share that prefix.
2. Start building the square word by word.
3. To find the i-th word, look at the first i characters of the i-th column (which are already determined by the first i-1 words).
4. Use the Trie to quickly find all words that start with that specific prefix.
5. Recurse until the square is full.

Example explanation

Words: ["ball", "area", "lead", "lady"].

1. Choose ball.
2. Second word must start with a (2nd char of ball). Option: area.
3. Third word must start with le (3rd chars of ball and area). Option: lead.
4. Fourth word must start with lady (4th chars of ball, area, lead). Option: lady. Square:

b a l l
a r e a
l e a d
l a d y

(Check: Row 3 is lead, Col 3 is l, e, a, d. Correct!)

Common mistakes candidates make

• O(N^K) Search: Trying every combination of words without using the prefix constraint.
• Prefix lookup speed: Not using a Trie or a Map to group words by prefix, leading to slow search times for each row.
• Empty results: Forgetting to return an empty list if no squares can be formed.

Interview preparation tip

In backtracking problems where you need to "find all words starting with X," a Trie is almost always the right answer. Practice the variant where you store word indices at each Trie node for faster retrieval.