3799. Word Squares II

MediumArrayStringBacktrackingEnumerationSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string array words, where every element is a distinct 4-letter string made up of lowercase English letters.

Your task is to build all possible word squares. A word square is formed by selecting 4 distinct words from the array and assigning them to four roles: top, left, right, and bottom. These four words are arranged to outline a 4 × 4 grid as follows:

top is placed along the top row (read left to right).
bottom is placed along the bottom row (read left to right).
left forms the left column (read top to bottom).
right forms the right column (read top to bottom).

Because the rows and columns share corner cells, the four words must agree at those shared corners. Specifically, the following conditions must all hold:

top[0] == left[0] — the top-left corner is shared by the top row and the left column.
top[3] == right[0] — the top-right corner is shared by the top row and the right column.
bottom[0] == left[3] — the bottom-left corner is shared by the bottom row and the left column.
bottom[3] == right[3] — the bottom-right corner is shared by the bottom row and the right column.

Note that the four chosen words top, left, right, and bottom must be distinct from one another.

Return all valid distinct word squares. Each result should be represented as the 4-tuple (top, left, right, bottom), and the full list of results must be sorted in ascending lexicographic order by that 4-tuple.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Brute force / Backtracking?

This problem maps to Brute force / Backtracking through a short path in the full flowchart.

Enumerating all possibilities with backtracking works for small input sizes.

Open in Flowchart

Show step-by-step reasoning

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

No: The problem deals with arranging strings into a grid; it does not involve nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

No: The problem asks for all valid word squares, not the kth smallest or largest element.

Involves Linked Lists?

No: The problem operates on an array of strings, with no linked list structures.

Does the problem have small constraints?

Yes: We are selecting and arranging 4 distinct words to satisfy corner-matching conditions, and the search space of word combinations is explored exhaustively, which fits problems with small constraints.

Brute force / Backtracking?

Yes: We need to enumerate combinations of words for the top, left, right, and bottom roles, ensuring distinctness and validating the shared-corner constraints at each step. This naturally maps to a brute force / backtracking exploration.

Conclusion: The flowchart suggests using a Backtracking approach to systematically build and validate all distinct word squares from the given words.

Intuition

The core observation is that a word square is fully determined by choosing 4 distinct words and assigning each to one of the four roles: top, left, right, and bottom. Once these four words are fixed, the entire 4 × 4 outline is decided, and we only need to verify that the four shared corner cells agree.

Let's think about what "agree" means. The grid has four corners, and each corner belongs to both a row word and a column word:

The top-left corner is the first letter of top and the first letter of left, so top[0] == left[0].
The top-right corner is the last letter of top and the first letter of right, so top[3] == right[0].
The bottom-left corner is the first letter of bottom and the last letter of left, so bottom[0] == left[3].
The bottom-right corner is the last letter of bottom and the last letter of right, so bottom[3] == right[3].

Because we have no extra structure to exploit and the input is small, the most direct idea is to try every possible assignment of words to the four roles. We pick a word for top, then a different word for left, then another different word for right, and finally a different word for bottom. This is exactly the brute force / backtracking pattern: we explore all 4-permutations of distinct words.

For each complete assignment, we simply check the four corner conditions. If all of them hold, the four words form a valid word square, so we record the tuple (top, left, right, bottom).

Finally, the problem asks for results in ascending lexicographic order by the 4-tuple. The neat trick is to sort words first. Since we iterate top, then left, then right, then bottom in the order of the sorted array (in that nesting order), the valid tuples are naturally generated in sorted order, so no extra sorting of the answers is needed.

Pattern Learn more about Backtracking and Sorting patterns.

Solution Approach

We implement the brute force / backtracking idea directly with nested loops, where each loop level fixes one role of the word square.

Step 1: Sort the words.

words.sort()
n = len(words)
ans = []

Sorting words up front is the key to getting the output already in ascending lexicographic order. Because the loops below iterate over indices in increasing order, and the nesting order is top → left → right → bottom, every valid tuple (top, left, right, bottom) is produced in sorted order automatically.

Step 2: Enumerate the four roles with four nested loops.

We loop over four indices i, j, k, h, each ranging over range(n). Each index selects one word:

i selects top = words[i]
j selects left = words[j]
k selects right = words[k]
h selects bottom = words[h]

for i in range(n):
    top = words[i]
    for j in range(n):
        if j != i:
            left = words[j]
            for k in range(n):
                if k != j and k != i:
                    right = words[k]
                    for h in range(n):
                        if h != k and h != j and h != i:
                            bottom = words[h]

Step 3: Enforce distinctness.

The four words must be distinct, so at every level we skip indices that were already used. The conditions j != i, then k != j and k != i, then h != k and h != j and h != i guarantee no word is reused across the four roles.

Step 4: Check the corner conditions.

Once a full assignment of four distinct words is chosen, we verify all four shared-corner constraints:

if (
    top[0] == left[0]
    and top[3] == right[0]
    and bottom[0] == left[3]
    and bottom[3] == right[3]
):
    ans.append([top, left, right, bottom])

top[0] == left[0] checks the top-left corner.
top[3] == right[0] checks the top-right corner.
bottom[0] == left[3] checks the bottom-left corner.
bottom[3] == right[3] checks the bottom-right corner.

If every condition holds, the four words form a valid word square, and we append the tuple [top, left, right, bottom] to ans.

Step 5: Return the answer.

return ans

Since the words were sorted and traversed in nested role order, ans is already sorted by the 4-tuple (top, left, right, bottom), so we return it directly.

Complexity.

The four nested loops over n words give a time complexity of O(n^4), with constant-time corner checks at the innermost level. The data structures used are just the sorted list words and the result list ans, so the extra space (beyond the output) is O(1).

Example Walkthrough

Let's walk through a small example to see how the brute force / backtracking approach builds word squares.

Input:

words = ["abca", "bdeb", "abde", "acea"]

Step 1: Sort the words.

After words.sort(), the array becomes:

["abca", "abde", "acea", "bdeb"]
#   0       1       2       3

We set n = 4 and ans = []. Sorting up front means any valid tuple we discover will already be in ascending lexicographic order.

Step 2-3: Enumerate roles with distinctness.

We try every ordered selection of 4 distinct indices for the roles top → left → right → bottom. Let's focus on a promising assignment and check it against the corners.

Candidate: i=0, j=1, k=3, h=2

This picks:

top = words[0] = "abca"
left = words[1] = "abde"
right = words[3] = "bdeb"
bottom = words[2] = "acea"

All four indices 0, 1, 3, 2 are distinct, so the distinctness conditions pass.

Step 4: Check the four corner conditions.

Let's visualize the 4 × 4 outline these words produce:

        top = a b c a
              ↑       ↑
left = a      a . . b      b = right
       b      b . . d      d
       d      d . . e      e
       e      e . . b      b
              ↓       ↓
     bottom = a c e a

Now verify each shared corner:

Corner	Condition	Values	Holds?
top-left	`top[0] == left[0]`	`'a' == 'a'`	✅
top-right	`top[3] == right[0]`	`'a' == 'b'`	❌

The top-right corner fails (top[3] = 'a' but right[0] = 'b'), so this assignment is rejected and nothing is appended.

A valid candidate: i=0, j=1, k=2, h=2... but h cannot equal k. Let's instead try i=0, j=1, k=3, h=3 — rejected since h == k.

Consider the assignment that does satisfy every corner. Take:

top = "abca" → top[0]='a', top[3]='a'
left = "acea" → left[0]='a', left[3]='a'
right = "abde" → right[0]='a', right[3]='e'
bottom = "abde" ... not distinct from right, rejected.

This illustrates the heart of the algorithm: most assignments fail a corner check or the distinctness rule, and only those passing all four corner conditions with four distinct words are recorded.

For the assignment top="abca", left="acea", right="...", bottom="...", the checks proceed exactly the same way:

top[0] == left[0] → top-left corner.
top[3] == right[0] → top-right corner.
bottom[0] == left[3] → bottom-left corner.
bottom[3] == right[3] → bottom-right corner.

Each valid 4-tuple is appended as [top, left, right, bottom].

Step 5: Return.

Because we iterated indices in increasing order with nesting top → left → right → bottom, every appended tuple lands in ans already sorted lexicographically. We return ans directly without any post-sorting.

Key takeaways from the walkthrough:

The grid is fully determined the moment four words are assigned to the four roles — only the corners need validation.
The distinctness checks (j != i, k != j and k != i, etc.) prune reused words early.
Sorting first means the natural enumeration order gives a sorted result for free.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4
5class Solution:
6    def wordSquares(self, words: List[str]) -> List[List[str]]:
7        # Edge case: empty input
8        if not words:
9            return []
10
11        word_length = len(words[0])
12        results: List[List[str]] = []
13
14        # Build a prefix-to-words map so we can quickly find all words
15        # that start with a given prefix.
16        prefix_to_words: defaultdict = defaultdict(list)
17        for word in words:
18            # Register the word under every one of its prefixes.
19            for i in range(word_length):
20                prefix_to_words[word[:i]].append(word)
21
22        def get_words_with_prefix(prefix: str) -> List[str]:
23            # Return all candidate words sharing the given prefix.
24            return prefix_to_words.get(prefix, [])
25
26        def backtrack(step: int, square: List[str]) -> None:
27            # If we have placed a word in every row, we found a valid square.
28            if step == word_length:
29                results.append(square[:])
30                return
31
32            # The next word must match the column constraint:
33            # its prefix is formed by the characters at column `step`
34            # of every word already placed.
35            prefix = "".join(word[step] for word in square)
36
37            # Try each candidate word that satisfies the prefix constraint.
38            for candidate in get_words_with_prefix(prefix):
39                square.append(candidate)
40                backtrack(step + 1, square)
41                square.pop()  # Undo the choice (backtrack).
42
43        # Start a search rooted at each word as the first row.
44        for word in words:
45            backtrack(1, [word])
46
47        return results
48

1class Solution {
2    /**
3     * Finds all quadruples of four distinct words (top, left, right, bottom)
4     * whose corner characters align to form a square border.
5     *
6     * Layout of the four words around the square:
7     *
8     *     top[0] ........ top[3]
9     *     left[0]          right[0]
10     *     ...                ...
11     *     left[3]          right[3]
12     *     bottom[0] .... bottom[3]
13     *
14     * Corner constraints:
15     *   - top[0]    == left[0]    (top-left corner)
16     *   - top[3]    == right[0]   (top-right corner)
17     *   - bottom[0] == left[3]    (bottom-left corner)
18     *   - bottom[3] == right[3]   (bottom-right corner)
19     *
20     * Assumes every word has length 4.
21     *
22     * @param words the input word list
23     * @return all valid quadruples in [top, left, right, bottom] order
24     */
25    public List<List<String>> wordSquares(String[] words) {
26        // Sort to produce results in a deterministic, lexicographic order.
27        Arrays.sort(words);
28
29        int n = words.length;
30        List<List<String>> ans = new ArrayList<>();
31
32        // Choose the top word.
33        for (int i = 0; i < n; i++) {
34            String top = words[i];
35
36            // Choose the left word (must differ from top).
37            for (int j = 0; j < n; j++) {
38                if (j == i) {
39                    continue;
40                }
41                String left = words[j];
42
43                // Early pruning: top-left corner must match.
44                if (top.charAt(0) != left.charAt(0)) {
45                    continue;
46                }
47
48                // Choose the right word (must differ from top and left).
49                for (int k = 0; k < n; k++) {
50                    if (k == i || k == j) {
51                        continue;
52                    }
53                    String right = words[k];
54
55                    // Early pruning: top-right corner must match.
56                    if (top.charAt(3) != right.charAt(0)) {
57                        continue;
58                    }
59
60                    // Choose the bottom word (must differ from the other three).
61                    for (int h = 0; h < n; h++) {
62                        if (h == i || h == j || h == k) {
63                            continue;
64                        }
65                        String bottom = words[h];
66
67                        // Verify the two bottom corners.
68                        if (bottom.charAt(0) == left.charAt(3)
69                                && bottom.charAt(3) == right.charAt(3)) {
70                            ans.add(List.of(top, left, right, bottom));
71                        }
72                    }
73                }
74            }
75        }
76
77        return ans;
78    }
79}
80

1class Solution {
2public:
3    vector<vector<string>> wordSquares(vector<string>& words) {
4        // Sort the words to produce results in a deterministic order.
5        ranges::sort(words);
6        const int wordCount = static_cast<int>(words.size());
7        vector<vector<string>> result;
8
9        // Choose the TOP border word.
10        for (int topIdx = 0; topIdx < wordCount; ++topIdx) {
11            const string& top = words[topIdx];
12
13            // Choose the LEFT border word (must differ from TOP).
14            for (int leftIdx = 0; leftIdx < wordCount; ++leftIdx) {
15                if (leftIdx == topIdx) {
16                    continue;
17                }
18                const string& left = words[leftIdx];
19
20                // Choose the RIGHT border word (must differ from TOP and LEFT).
21                for (int rightIdx = 0; rightIdx < wordCount; ++rightIdx) {
22                    if (rightIdx == leftIdx || rightIdx == topIdx) {
23                        continue;
24                    }
25                    const string& right = words[rightIdx];
26
27                    // Choose the BOTTOM border word (must differ from all others).
28                    for (int bottomIdx = 0; bottomIdx < wordCount; ++bottomIdx) {
29                        if (bottomIdx == rightIdx ||
30                            bottomIdx == leftIdx ||
31                            bottomIdx == topIdx) {
32                            continue;
33                        }
34                        const string& bottom = words[bottomIdx];
35
36                        // Verify that the four corners match:
37                        //   - top-left:     top[0]    == left[0]
38                        //   - top-right:    top[3]    == right[0]
39                        //   - bottom-left:  bottom[0] == left[3]
40                        //   - bottom-right: bottom[3] == right[3]
41                        const bool cornersMatch =
42                            top.front()    == left.front()  &&
43                            top.back()     == right.front() &&
44                            bottom.front() == left.back()   &&
45                            bottom.back()  == right.back();
46
47                        if (cornersMatch) {
48                            result.push_back({top, left, right, bottom});
49                        }
50                    }
51                }
52            }
53        }
54        return result;
55    }
56};
57```
58
59**Key improvements made:**
60
611. **Descriptive loop variables** — `i, j, k, h` became `topIdx, leftIdx, rightIdx, bottomIdx`, making each border's role explicit.
622. **`const string&` references** — avoids copying each word on every iteration (the original copied strings repeatedly).
633. **Early `continue`** — replaced deep nested `if` blocks with guard clauses, flattening the structure.
644. **`front()` / `back()`** — clearer than magic indices `[0]` and `[3]` for accessing corners.
655. **Explicit `cornersMatch` boolean** — documents exactly which corners are being compared.
66
67---
68
69**An important perspective worth raising:**
70
71This implementation does **not** solve the actual LeetCode 425 problem. That problem requires a full square where `square[i][j] == square[j][i]` for all cells, built from words of length `k`. The standard, efficient approach uses a **Trie + backtracking**:
72
73```cpp
74class Solution {
75    struct TrieNode {
76        TrieNode* children[26] = {};
77        vector<int> wordIndices;  // words passing through this node
78    };
79
80public:
81    vector<vector<string>> wordSquares(vector<string>& words) {
82        TrieNode root;
83        for (int i = 0; i < (int)words.size(); ++i) {
84            TrieNode* node = &root;
85            for (char c : words[i]) {
86                int idx = c - 'a';
87                if (!node->children[idx]) node->children[idx] = new TrieNode();
88                node = node->children[idx];
89                node->wordIndices.push_back(i);
90            }
91        }
92
93        int len = words.empty() ? 0 : words[0].size();
94        vector<vector<string>> result;
95        vector<string> square;
96
97        function<void()> backtrack = [&]() {
98            int row = square.size();
99            if (row == len) { result.push_back(square); return; }
100
101            // Build the prefix that the next word must match (column constraint).
102            string prefix;
103            for (int r = 0; r < row; ++r) prefix += square[r][row];
104
105            // Find candidate words sharing this prefix via the Trie.
106            TrieNode* node = &root;
107            for (char c : prefix) {
108                node = node->children[c - 'a'];
109                if (!node) return;
110            }
111            for (int wi : node->wordIndices) {
112                square.push_back(words[wi]);
113                backtrack();
114                square.pop_back();
115            }
116        };
117
118        for (const string& w : words) {
119            square.push_back(w);
120            backtrack();
121            square.pop_back();
122        }
123        return result;
124    }
125};
126

1/**
2 * Finds combinations of four words that form a bordered square frame.
3 *
4 * The square frame is laid out as follows (each word has length 4):
5 *
6 *   top:    T0 T1 T2 T3
7 *   left:   L0 .. .. L3      right:  R0 .. .. R3
8 *   bottom: B0 B1 B2 B3
9 *
10 * The matching conditions for the four corners are:
11 *   - top[0]    === left[0]     (top-left corner)
12 *   - top[3]    === right[0]    (top-right corner)
13 *   - bottom[0] === left[3]     (bottom-left corner)
14 *   - bottom[3] === right[3]    (bottom-right corner)
15 *
16 * @param words - The list of candidate words.
17 * @returns All valid [top, left, right, bottom] combinations.
18 */
19function wordSquares(words: string[]): string[][] {
20    // Sort lexicographically so results are produced in a stable order.
21    words.sort();
22
23    const wordCount: number = words.length;
24    const result: string[][] = [];
25
26    // Choose the top word.
27    for (let topIndex = 0; topIndex < wordCount; topIndex++) {
28        const top: string = words[topIndex];
29
30        // Choose the left word (must differ from top).
31        for (let leftIndex = 0; leftIndex < wordCount; leftIndex++) {
32            if (leftIndex === topIndex) {
33                continue;
34            }
35            const left: string = words[leftIndex];
36
37            // Choose the right word (must differ from top and left).
38            for (let rightIndex = 0; rightIndex < wordCount; rightIndex++) {
39                if (rightIndex === leftIndex || rightIndex === topIndex) {
40                    continue;
41                }
42                const right: string = words[rightIndex];
43
44                // Choose the bottom word (must differ from the previous three).
45                for (let bottomIndex = 0; bottomIndex < wordCount; bottomIndex++) {
46                    if (
47                        bottomIndex === rightIndex ||
48                        bottomIndex === leftIndex ||
49                        bottomIndex === topIndex
50                    ) {
51                        continue;
52                    }
53                    const bottom: string = words[bottomIndex];
54
55                    // Verify all four corners line up to form a valid frame.
56                    const topLeftMatches: boolean = top[0] === left[0];
57                    const topRightMatches: boolean = top[3] === right[0];
58                    const bottomLeftMatches: boolean = bottom[0] === left[3];
59                    const bottomRightMatches: boolean = bottom[3] === right[3];
60
61                    if (
62                        topLeftMatches &&
63                        topRightMatches &&
64                        bottomLeftMatches &&
65                        bottomRightMatches
66                    ) {
67                        result.push([top, left, right, bottom]);
68                    }
69                }
70            }
71        }
72    }
73
74    return result;
75}
76

Time and Space Complexity

Time Complexity: O(n^4)

The code uses four nested loops, each iterating over all n words in the list:

The outermost loop (i) runs n times to select top.
The second loop (j) runs n times to select left.
The third loop (k) runs n times to select right.
The innermost loop (h) runs n times to select bottom.

This results in n × n × n × n = n^4 iterations. Inside the innermost loop, the work performed is constant: a fixed number of character comparisons (the index-checking conditions like j != i and the four equality checks top[0] == left[0], etc., are all O(1) operations).

Additionally, words.sort() at the beginning costs O(n log n × L) where L is the word length, but this is dominated by the O(n^4) term. Therefore, the overall time complexity is O(n^4).

Space Complexity: O(1) (excluding output) / O(n^4) (including output)

The auxiliary space used by the algorithm itself is O(1), since only a constant number of variables (top, left, right, bottom, loop indices) are maintained. The sorting may use O(n) or O(log n) auxiliary space depending on the implementation.
If the output list ans is counted, in the worst case the number of valid word squares appended could be on the order of O(n^4), since up to that many combinations could satisfy the conditions. Each stored square occupies constant space (4 words), so the output space is O(n^4).

Thus, the dominant space cost comes from the result storage, giving O(n^4) including output, or O(n) auxiliary space when excluding the output (due to sorting).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Submitting code that solves a completely different problem than the one described.

The biggest trap here is that the Python code does not solve the stated problem at all. The problem asks you to build a hollow word square — four words arranged on the outline (top row, bottom row, left column, right column) of a 4×4 grid, agreeing only at the four corners. The provided code, however, implements the classic dense "Word Squares" problem, where word k read horizontally must equal column k read vertically across all rows.

Concretely, the code diverges in three critical ways:

Wrong constraint model. The line
```
prefix = "".join(word[step] for word in square)
```
forces every placed word to match a column-by-column prefix, i.e. square[r][c] == square[c][r] for all cells. That is the full word-square symmetry condition, which is far stronger than the four corner equalities the problem requires.
Wrong number of words / roles. The intended problem fixes exactly 4 distinct words in named roles (top, left, right, bottom). The code instead builds a square with word_length rows (one word per row) and never distinguishes the four roles, nor returns a (top, left, right, bottom) tuple.
Missing distinctness enforcement. The problem demands the four chosen words be distinct from one another. The code allows the same word to be reused across rows, so it neither checks nor guarantees distinctness.

The net effect: even on small inputs the code produces results in the wrong shape (lists of 4 row-words under dense constraints) and wrong content (it rejects valid hollow squares and accepts dense ones the problem never asked for).

Solution

Implement the algorithm that actually matches the problem statement — the O(n^4) brute force over the four roles, with explicit distinctness and corner checks. Sorting first yields output already in ascending lexicographic order:

from typing import List, Tuple


class Solution:
    def wordSquares(self, words: List[str]) -> List[Tuple[str, str, str, str]]:
        words = sorted(words)
        n = len(words)
        ans: List[Tuple[str, str, str, str]] = []

        for i in range(n):
            top = words[i]
            for j in range(n):
                if j == i:
                    continue
                left = words[j]
                # Top-left corner must agree before going deeper.
                if top[0] != left[0]:
                    continue
                for k in range(n):
                    if k == i or k == j:
                        continue
                    right = words[k]
                    # Top-right corner.
                    if top[3] != right[0]:
                        continue
                    for h in range(n):
                        if h == i or h == j or h == k:
                            continue
                        bottom = words[h]
                        # Bottom-left and bottom-right corners.
                        if bottom[0] == left[3] and bottom[3] == right[3]:
                            ans.append((top, left, right, bottom))
        return ans

Why this is correct and efficient:

Correct shape & roles. It returns 4-tuples (top, left, right, bottom), exactly as specified.
Correct constraints. Only the four corner equalities are enforced — no spurious dense-square symmetry.
Distinctness. The continue guards (j == i, k in {i, j}, h in {i, j, k}) ensure all four words are different.
Sorted output for free. Because words is sorted and the loops nest in role order top → left → right → bottom over increasing indices, the tuples are generated in ascending lexicographic order, so no final sort is needed.
Early pruning. Hoisting the top[0] != left[0] and top[3] != right[0] checks out of the inner loops avoids wasted iterations, keeping the constant factor small even though the worst case stays O(n^4).

Verification tip: Always re-read the problem's output format and constraint definition before trusting a solution snippet. A quick sanity test — feeding a tiny words list and confirming the returned tuples really are (top, left, right, bottom) satisfying only the four corner rules — would immediately expose the mismatch in the original code.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering