LeetCode 425: Word Squares Solution in Python – A Step-by-Step Guide

Imagine you’re handed a list of words—like ["area", "lead", "wall", "lady", "ball"]—and your challenge is to arrange them into a square where each row is a word, and each column reads down to form the same words. For example, stack "area", "read", "eats", "aids" (if all were in the list), and you’d get a 4×4 square where rows and columns match perfectly. That’s the fascinating puzzle of LeetCode 425: Word Squares, a hard-level problem that’s all about building symmetric word grids. Using Python, we’ll tackle it two ways: the Best Solution, a Trie with backtracking approach that finds squares efficiently, and an Alternative Solution, a brute force method with permutation checking that tries all combos. With examples, code, and a friendly vibe, this guide will help you square those words, whether you’re new to coding or ready for a tough challenge. Let’s stack those letters and dive in!

What Is LeetCode 425: Word Squares?

In LeetCode 425: Word Squares, you’re given a list of strings words (e.g., ["area", "lead", "wall", "lady", "ball"]), all of the same length, and you need to return all possible word squares that can be formed. A word square is an n × n grid where:

Each row is a word from words.
Each column, read vertically, is also a word from words.

For example, with ["area", "lead", "wall", "lady", "ball"], one valid square is [["ball", "area", "lead", "lady"]] (check: columns "ball", "area", "lead", "lady" match rows). Your task is to return all such squares as a list of lists of strings. Words can be reused, and the output can be in any order.

Problem Statement

Input: A list of strings words, all of length n.
Output: A list of lists of strings—all valid word squares.
Rules:

Each row and column must be a word from words.
Grid must be n × n, where n is the word length.
Words can be reused.

Constraints

1 <= words.length <= 1000.
1 <= words[i].length <= 5.
All words[i] have the same length.
words[i] consists of lowercase English letters.
All words[i] are unique.

Examples

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

Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]].

Input: words = ["abat","baba","atan","atal"]

Output: [["baba","abat","baba","atal"],["baba","abat","baba","atan"]].

Input: words = ["abc","def","ghi"]

Output: [["abc","def","ghi"]].

Understanding the Problem: Building the Square

To solve LeetCode 425: Word Squares in Python, we need to find all n × n grids where each row and column is a word from words. A naive idea might be to try every possible combination—but with up to 1000 words of length 5, that’s a combinatorial explosion! Instead, we’ll use:

Best Solution (Trie with Backtracking): O(n * 26^n) time, O(n * |words|) space—optimizes with a Trie.
Alternative Solution (Brute Force with Permutation Checking): O(n! * n) time, O(n²)—tries all permutations.

Let’s dive into the Trie-based solution with a clear, step-by-step explanation.

Best Solution: Trie with Backtracking

Why This Is the Best Solution

The Trie with backtracking method is the top pick because it’s efficient—O(n * 26^n) time, O(n * |words|) space—and cleverly uses a Trie to prune invalid paths while building the square row-by-row. It stores words in a Trie for fast prefix lookups, then backtracks to explore all valid squares, ensuring each row fits the growing column constraints. It’s like assembling a puzzle, snapping pieces in place with a smart guide!

How It Works

Think of the words as puzzle pieces you’re stacking:

Step 1: Build the Trie:

Insert each word into a Trie (e.g., "area" → a-r-e-a).
Store full words at leaf nodes for prefix matches.

Step 2: Backtrack to Build Square:

Start with an empty square (list).
For each row:

Get current prefix from column (e.g., row 1, prefix = "b" from "ball").
Find all words in Trie with that prefix (e.g., "baba", "ball").
Add each, recurse to next row, backtrack if fails.

Step 3: Collect Results:

When square is n × n, add to result list.

Step 4: Why This Works:

Trie cuts search space by prefix matching.
Backtracking ensures all valid combos are found.
It’s like growing a word grid with a prefix compass!

Step-by-Step Example

Example: `words = ["area","lead","wall","lady","ball"]`

Trie:

a → r → e → a ("area").
l → e → a → d ("lead"), a → d → y ("lady").
w → a → l → l ("wall").
b → a → l → l ("ball").

Backtrack (n = 4):

Row 0: Try "area", square = ["area"].

Prefix "" → all words, pick "area".

Row 1: Prefix "r" (col 1), "read" not in list, try "lady", square = ["area", "lady"].

Prefix "r" → no match, try next word.

Row 2: Prefix "ea", "lead" fits, square = ["area", "lady", "lead"].
Row 3: Prefix "aly", "lady" fits, square = ["area", "lady", "lead", "lady"].

Check cols: "alld", "real", "lady", "dyad" → only "lady" matches, adjust.

Try "ball" start: ["ball", "area", "lead", "lady"] → all match.

Result: [["ball", "area", "lead", "lady"], ["wall", "area", "lead", "lady"]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

class TrieNode:
    def __init__(self):
        self.children = {}  # Map char to next node
        self.words = []     # Words with this prefix

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        # Step 1: Build Trie
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                node.words.append(word)

        # Step 2: Backtrack to build squares
        n = len(words[0])
        result = []

        def backtrack(square):
            if len(square) == n:
                result.append(square[:])
                return
            # Get prefix for current row from columns
            prefix = ""
            r = len(square)
            for row in square:
                prefix += row[r]
            # Find matching words
            node = root
            for char in prefix:
                if char not in node.children:
                    return
                node = node.children[char]
            # Try each candidate
            for candidate in node.words:
                square.append(candidate)
                backtrack(square)
                square.pop()

        # Step 3: Start with each word
        for word in words:
            backtrack([word])

        return result

Line 1-4: TrieNode class:

children: Map for next chars.
words: List of words with prefix ending here.

Line 8-17: Build Trie:

Line 10-16: For each word, add to Trie, append to words at each node.

Line 20-38: Backtrack:

Line 22-24: If square is n × n, add copy to result.
Line 26-30: Build prefix from current column (e.g., "b" from "ball").
Line 32-35: Traverse Trie with prefix, stop if no match.
Line 37-40: Try each candidate word, recurse, backtrack.

Line 41-43: Start with each word as first row.
Line 45: Return all valid squares.
Time Complexity: O(n * 26^n)—n rows, up to 26 choices per row, Trie reduces branches.
Space Complexity: O(n * |words|)—Trie storage.

This is like assembling a word puzzle with a prefix-guided robot!

Alternative Solution: Brute Force with Permutation Checking

Why an Alternative Approach?

The brute force with permutation checking method generates all possible n-word permutations and checks if each forms a valid square. It’s O(n! * n) time and O(n²) space—simple but impractical for large lists. It’s like trying every seating arrangement at a table until the words align!

How It Works

Picture it as shuffling words:

Step 1: Generate all n-word permutations.
Step 2: For each, check if rows = columns.
Step 3: Collect valid squares.

Step-by-Step Example

Example: `words = ["ball","area","lead","lady"]`

Permutations (n=4):

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

Cols: "ball", "area", "lead", "lady" → match ✓.

["wall", "area", "lead", "lady"] (if in list):

Cols: "wall", "area", "lead", "lady" → match ✓.

Result: All valid permutations.

Code for Brute Force (Simplified)

from itertools import permutations

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        n = len(words[0])
        result = []

        def is_valid_square(square):
            for c in range(n):
                col = "".join(square[r][c] for r in range(n))
                if col != square[c]:
                    return False
            return True

        # Try all permutations (simplified, not full)
        for perm in permutations(words, n):
            square = list(perm)
            if is_valid_square(square):
                result.append(square)

        return result

# Note: Full brute force would check all combos, too slow.

Time Complexity: O(n! * n)—permutations and checking.
Space Complexity: O(n²)—store square.

It’s a slow square-shuffler!

Comparing the Two Solutions

Trie with Backtracking (Best):

Pros: O(n * 26^n), O(n * |words|), fast with pruning.
Cons: Trie setup.

Brute Force (Alternative):

Pros: O(n! * n), O(n²), simple.
Cons: Too slow.

Trie wins for speed.

Additional Examples and Edge Cases

["a"]: [["a"]].
["ab","ba"]: [["ab","ba"], ["ba","ab"]].
["abc"]: [["abc"]].

Trie handles all.

Complexity Breakdown

Trie: Time O(n * 26^n), Space O(n * |words|).
Brute Force: Time O(n! * n), Space O(n²).

Trie’s the champ.

Key Takeaways

Trie: Prefix power!
Brute Force: Shuffle it all!
Squares: Symmetry rules.
Python Tip: Dicts rock—see [Python Basics](/python/basics).

Final Thoughts: Square Those Words

LeetCode 425: Word Squares in Python is a word-stacking quest. Trie with backtracking builds it fast, while brute force shuffles it slow. Want more word fun? Try LeetCode 212: Word Search II or LeetCode 422: Valid Word Square. Ready to stack? Head to Solve LeetCode 425 on LeetCode and square those words today!

LeetCode 425: Word Squares Solution in Python – A Step-by-Step Guide

What Is LeetCode 425: Word Squares?

Problem Statement

Constraints

Examples

Understanding the Problem: Building the Square

Best Solution: Trie with Backtracking

Why This Is the Best Solution

How It Works

Step-by-Step Example

Example: words = ["area","lead","wall","lady","ball"]

Code with Detailed Line-by-Line Explanation

Alternative Solution: Brute Force with Permutation Checking

Why an Alternative Approach?

How It Works

Step-by-Step Example

Example: words = ["ball","area","lead","lady"]

Code for Brute Force (Simplified)

Comparing the Two Solutions

Additional Examples and Edge Cases

Complexity Breakdown

Key Takeaways

Final Thoughts: Square Those Words

Example: `words = ["area","lead","wall","lady","ball"]`

Example: `words = ["ball","area","lead","lady"]`