LeetCode Problem 3799

Difficulty: 🟡 Medium
Topics: Array, String, Backtracking, Sorting, Enumeration

Solution

LeetCode 3799 - Word Squares II

Problem Understanding

We are given an array of distinct 4-letter words. Our goal is to construct every valid word square consisting of exactly four different words:

• top forms the top row.
• bottom forms the bottom row.
• left forms the left column.
• right forms the right column.

Since each word has length 4, only the four corner positions matter. The arrangement must satisfy these corner constraints:

• top[0] == left[0]
• top[3] == right[0]
• bottom[0] == left[3]
• bottom[3] == right[3]

All four selected words must be distinct.

The input is a list of distinct lowercase strings, each of length 4. We must return every valid square as a 4-element array:

[top, left, right, bottom]

The final result must be sorted lexicographically according to this 4-tuple ordering.

The constraints are quite small:

• Number of words is at most 15.
• Every word has fixed length 4.
• All words are distinct.

These constraints immediately suggest that exhaustive search is possible, but we should still avoid checking every possible quadruple when a more structured search exists.

Some important observations:

• The words are distinct, so we never need to worry about duplicate entries in the input.
• Every valid square requires four different words.
• Only the four corner characters matter. The middle characters are irrelevant.
• Multiple valid squares can exist using the same set of words in different roles.
• The output must be lexicographically sorted, regardless of the order in which solutions are discovered.

Approaches

Brute Force

The most direct solution is to try every possible assignment of four distinct words:

(top, left, right, bottom)

For each quadruple, we check the four corner constraints:

top[0]    == left[0]
top[3]    == right[0]
bottom[0] == left[3]
bottom[3] == right[3]

If all constraints hold, we add the square to the answer.

This approach is correct because it explicitly examines every possible arrangement of four distinct words and accepts exactly those satisfying the required conditions.

However, its complexity is high. With up to 15 words, the number of ordered quadruples is:

15 × 14 × 13 × 12 = 32,760

While still manageable, we can do much better by exploiting the corner constraints during construction rather than after selecting all four words.

Key Insight

The corner constraints depend only on the first and last characters of each word.

Suppose we choose top and left.

Immediately, we already know:

top[0] == left[0]

must hold.

Once these two words are fixed:

• right must start with top[3].
• bottom must start with left[3].

Finally, the last condition requires:

bottom[3] == right[3]

Instead of enumerating all quadruples, we can build candidate groups incrementally.

A useful optimization is to index words by their starting character. Then, after choosing top and left, we can directly retrieve valid candidates for right and bottom rather than scanning the entire array.

Because only 15 words exist, this pruning dramatically reduces unnecessary checks while keeping the implementation simple.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(1) excluding output	Check every ordered quadruple
Optimal	O(n³)	O(n)	Use character indexing to prune candidates

Algorithm Walkthrough

Step 1

Create a hash map that groups words by their first character.

For example:

{
    'a': ["able", "area", ...],
    'e': ["echo", "edge", ...]
}

This allows us to quickly find words that can serve as the right or bottom side of a square.

Step 2

Iterate through every ordered pair (top, left).

Since all four words must be distinct, skip pairs where:

top == left

Also enforce the first corner constraint:

top[0] == left[0]

If this condition fails, no valid square can be built from this pair.

Step 3

Determine the required starting letters for the remaining two words.

For the right word:

right[0] = top[3]

For the bottom word:

bottom[0] = left[3]

Use the hash map to retrieve only words beginning with these required letters.

Step 4

Iterate through every candidate right.

Ensure it is distinct from both top and left.

Step 5

Iterate through every candidate bottom.

Ensure it is distinct from all previously chosen words.

Step 6

Check the final remaining corner constraint:

bottom[3] == right[3]

If true, a valid square has been found.

Add:

[top, left, right, bottom]

to the answer.

Step 7

After all possibilities have been explored, sort the answer lexicographically.

Return the sorted list.

Why it works

The algorithm systematically constructs every ordered assignment of four distinct words that can satisfy the corner constraints. The first three constraints are enforced while selecting candidates, and the final constraint is checked before accepting a square. Because every valid square must satisfy these conditions and every feasible combination is considered exactly once, the algorithm finds all valid squares and no invalid ones.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        start_map = defaultdict(list)

        for word in words:
            start_map[word[0]].append(word)

        result = []

        for top in words:
            for left in words:
                if top == left:
                    continue

                if top[0] != left[0]:
                    continue

                right_candidates = start_map[top[3]]
                bottom_candidates = start_map[left[3]]

                for right in right_candidates:
                    if right == top or right == left:
                        continue

                    for bottom in bottom_candidates:
                        if (
                            bottom == top
                            or bottom == left
                            or bottom == right
                        ):
                            continue

                        if bottom[3] == right[3]:
                            result.append(
                                [top, left, right, bottom]
                            )

        result.sort()
        return result

The implementation begins by building start_map, which groups words according to their first character. This allows efficient retrieval of words that satisfy the starting-character requirements for the right and bottom positions.

The nested loops first select top and left. Any pair violating the first corner constraint is discarded immediately.

Once top and left are fixed, the required first letters of right and bottom are known. Instead of scanning every word again, the algorithm retrieves only matching candidates from start_map.

For each candidate pair (right, bottom), the code verifies that all four words are distinct and checks the final corner condition. Every valid square is appended to the result.

Finally, the result list is sorted lexicographically before being returned.

Go Solution

func wordSquares(words []string) [][]string {
	startMap := make(map[byte][]string)

	for _, word := range words {
		startMap[word[0]] = append(startMap[word[0]], word)
	}

	var result [][]string

	for _, top := range words {
		for _, left := range words {
			if top == left {
				continue
			}

			if top[0] != left[0] {
				continue
			}

			rightCandidates := startMap[top[3]]
			bottomCandidates := startMap[left[3]]

			for _, right := range rightCandidates {
				if right == top || right == left {
					continue
				}

				for _, bottom := range bottomCandidates {
					if bottom == top ||
						bottom == left ||
						bottom == right {
						continue
					}

					if bottom[3] == right[3] {
						result = append(result, []string{
							top,
							left,
							right,
							bottom,
						})
					}
				}
			}
		}
	}

	for i := 0; i < len(result); i++ {
		for j := i + 1; j < len(result); j++ {
			a := result[i]
			b := result[j]

			swap := false

			for k := 0; k < 4; k++ {
				if a[k] < b[k] {
					break
				}
				if a[k] > b[k] {
					swap = true
					break
				}
			}

			if swap {
				result[i], result[j] = result[j], result[i]
			}
		}
	}

	return result
}

The Go solution follows the same algorithm as the Python version. A map from starting character to candidate words provides efficient filtering. The primary difference is explicit slice management and manual lexicographic sorting of the result tuples. Since the maximum number of solutions is small, a simple comparison-based sort is sufficient.

Worked Examples

Example 1

words = ["able","area","echo","also"]

Character Index

Start Character	Words
a	able, area, also
e	echo

Iteration 1

Choose:

top = "able"
left = "area"

Check:

top[0] = 'a'
left[0] = 'a'

Valid.

Required candidates:

right starts with 'e'
bottom starts with 'a'

So:

right_candidates = ["echo"]
bottom_candidates = ["able","area","also"]

Candidate Evaluation

right	bottom	Distinct?	bottom[3]	right[3]	Valid
echo	able	No	e	o	No
echo	area	No	a	o	No
echo	also	Yes	o	o	Yes

Result:

["able","area","echo","also"]

Iteration 2

Choose:

top = "area"
left = "able"

Required:

right starts with 'a'
bottom starts with 'e'

Candidates:

right = "also"
bottom = "echo"

Check:

bottom[3] = 'o'
right[3] = 'o'

Valid.

Result:

["area","able","also","echo"]

After sorting:

[
    ["able","area","echo","also"],
    ["area","able","also","echo"]
]

Example 2

words = ["code","cafe","eden","edge"]

Index:

Start Character	Words
c	code, cafe
e	eden, edge

Every possible (top, left) pair eventually fails one of the corner constraints.

No valid square is generated.

Output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	For each top-left pair, only matching right and bottom candidates are explored
Space	O(n)	Hash map storing words grouped by first character

The dominant cost comes from iterating through candidate combinations after fixing top and left. Since the alphabet size is fixed and words are distributed among character buckets, the average number of candidates is reduced substantially. The auxiliary space is the character-index map containing all input words.

Test Cases

sol = Solution()

# Example 1
assert sol.wordSquares(
    ["able", "area", "echo", "also"]
) == [
    ["able", "area", "echo", "also"],
    ["area", "able", "also", "echo"]
]

# Example 2
assert sol.wordSquares(
    ["code", "cafe", "eden", "edge"]
) == []

# Minimum size input with no solution
assert sol.wordSquares(
    ["abcd", "efgh", "ijkl", "mnop"]
) == []

# Single valid square
assert sol.wordSquares(
    ["aaaa", "abca", "axya", "aaaa"]
) == []
# duplicate words are not allowed by constraints

# Four words that form one square
assert sol.wordSquares(
    ["able", "area", "echo", "also"]
)

# Verify lexicographic ordering
ans = sol.wordSquares(
    ["able", "area", "echo", "also"]
)
assert ans == sorted(ans)

# Larger input containing unrelated words
assert sol.wordSquares(
    ["able", "area", "echo", "also",
     "xxxx", "yyyy", "zzzz"]
) == [
    ["able", "area", "echo", "also"],
    ["area", "able", "also", "echo"]
]

# Distinctness requirement stress test
assert sol.wordSquares(
    ["aaaa", "aaab", "aaba", "abaa"]
) == []

Test Summary

Test	Why
Example 1	Verifies multiple valid squares
Example 2	Verifies empty result
Completely unrelated words	No corner constraints can be satisfied
Lexicographic ordering check	Ensures final sorting is correct
Additional irrelevant words	Confirms extra words do not affect correctness
Distinctness stress test	Ensures all four words must be different
Minimum-sized input	Validates behavior at lower constraint boundary

Edge Cases

All Words Share the Same Starting Character

A large number of candidate combinations can arise when many words begin with the same letter. A buggy implementation might accidentally generate duplicate solutions or fail to enforce distinctness. This solution explicitly checks that all four selected words are different before accepting a square.

No Valid Top-Left Pair Exists

If no two words share the same first character, then the very first corner condition can never be satisfied. The algorithm immediately rejects such pairs and naturally returns an empty result.

Multiple Squares Using the Same Words

The same set of words may form different valid squares when assigned different roles. For example, a word that serves as top in one solution may serve as left in another. The algorithm treats every ordered assignment independently, ensuring all valid squares are discovered.

Candidate Buckets Are Empty

For some (top, left) pair, there may be no words beginning with the required character for right or bottom. In that case, the corresponding candidate list is empty and the nested loops simply perform no work. No special handling is required.

Output Ordering

Solutions may be discovered in an arbitrary traversal order. Since the problem requires lexicographic ordering by (top, left, right, bottom), the implementation performs a final sort before returning the answer, guaranteeing the required output format.