LeetCode 422: Valid Word Square Solution in Python – A Step-by-Step Guide

What Is LeetCode 422: Valid Word Square?

In LeetCode 422: Valid Word Square, you’re given a list of strings words (e.g., ["abcd", "bnrt", "crmy", "dtye"]), and you need to determine if they form a valid word square. A word square is valid if:

• The number of words equals the length of each word (forming an n × n grid).
• The kth row matches the kth column when read vertically.

For the example above, it’s a 4×4 square, and rows "abcd", "bnrt", etc., match columns "abcd", "bnrt", etc., so it’s valid (True). If rows and columns don’t align—like ["ball", "area", "lead", "lady"]—it’s False. Your job is to return a boolean indicating validity.

Problem Statement

• Input: A list of strings words.
• Output: A boolean—True if words forms a valid word square, False otherwise.
• Rules:
• Number of words = length of each word (n × n).
• kth row = kth column for all k.
• Words contain only lowercase English letters.

Constraints

• 1 <= words.length <= 500.
• 1 <= words[i].length <= 500.
• words[i] consists of lowercase English letters.

Examples

• Input: words = ["abcd","bnrt","crmy","dtye"]
• Output: True (rows match columns).
• Input: words = ["ball","area","lead","lady"]
• Output: False (e.g., row "ball" ≠ column "baal").
• Input: words = ["abc","b"]
• Output: False (not square, 2 ≠ 3).

Understanding the Problem: Checking the Square

To solve LeetCode 422: Valid Word Square in Python, we need to verify that words forms an n × n grid where each row equals its corresponding column when read vertically. A naive idea might be to build the full column strings and compare—but we can streamline it! We’ll use:

• Best Solution (Row-Column Comparison): O(n²) time, O(1) space—checks matches directly.
• Alternative Solution (Matrix Transposition): O(n²) time, O(n²) space—flips the grid.

Let’s dive into the row-column comparison solution with a clear, step-by-step explanation.

Best Solution: Row-Column Comparison

Why This Is the Best Solution

The row-column comparison method is the top pick because it’s efficient—O(n²) time, O(1) space (excluding input)—and straightforward. It checks each cell by comparing the row character (words[r][c]) with the column character (words[c][r]), skipping extra storage or full string builds. It’s like eyeballing the grid row-by-row, ensuring each letter mirrors its vertical twin!

How It Works

Think of the word list as a grid you’re inspecting:

• Step 1: Validate Square Shape:
• Check if number of words (n) equals length of first word.
• Ensure all words have length n.
• Step 2: Compare Row vs. Column:
• For each row r and column c:
• If c < len(words[r]), check words[r][c] vs. words[c][r].
• If r < len(words[c]), ensure symmetry holds.
• Mismatch or length issue → False.
• Step 3: Why This Works:
• Direct comparison catches any discrepancy.
• No extra space beyond input, just indices.
• It’s like flipping the grid in your mind without writing it out!

Step-by-Step Example

Example: words = ["abcd","bnrt","crmy","dtye"]

• Grid:

a b c d b n r t c r m y d t y e

• Validate: 4 words, each 4 chars, n = 4, square ✓.
• Check:
• (0,0): 'a' = 'a'.
• (0,1): 'b' = 'b'.
• (0,2): 'c' = 'c'.
• (0,3): 'd' = 'd'.
• (1,0): 'b' = 'b'.
• (1,1): 'n' = 'n'.
• (1,2): 'r' = 'r'.
• (1,3): 't' = 't'.
• (2,0): 'c' = 'c'.
• Continue: All match (e.g., (3,3): 'e' = 'e').
• Result: True.

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

• Grid:

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

• Check:
• (0,0): 'b' = 'b'.
• (0,1): 'a' = 'a'.
• (0,2): 'l' ≠ 'r', fail.
• Result: False.

Code with Detailed Line-by-Line Explanation

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

Copy codeclass Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        # Step 1: Validate square shape
        if not words or len(words) != len(words[0]):
            return False
        n = len(words)
        for word in words:
            if len(word) != n:
                return False

        # Step 2: Compare row vs. column
        for r in range(n):
            for c in range(len(words[r])):
                # Check if column index c has row r and matches
                if c >= len(words) or r >= len(words[c]) or \
                   words[r][c] != words[c][r]:
                    return False

        return True

• Line 4-9: Validate square:
• Line 4: Empty or not n × n (e.g., words vs. words[0]), False.
• Line 6-9: Each word must be length n (e.g., all 4), else False.
• Line 12-16: Compare:
• Line 12-13: Loop through row r, column c in words[r].
• Line 14-15: Check:
• c < len(words): Column exists.
• r < len(words[c]): Row exists in column word.
• words[r][c] == words[c][r]: Characters match.
• Any fail → False.
• Line 18: All checks pass, return True.
• Time Complexity: O(n²)—n rows, up to n chars each.
• Space Complexity: O(1)—no extra space beyond input.

This is like checking a crossword grid with a quick eye!

Alternative Solution: Matrix Transposition

Why an Alternative Approach?

The matrix transposition method builds the columns explicitly by flipping the grid, then compares rows to columns as full strings. It’s O(n²) time and O(n²) space—more visual but uses extra memory. It’s like writing out the vertical words to see if they match the horizontal ones!

How It Works

Picture it as flipping the grid:

• Step 1: Validate square shape.
• Step 2: Build transposed columns (e.g., "abcd" → "abcd", "bnrt" → "bnrt").
• Step 3: Compare original rows to transposed columns.

Step-by-Step Example

Example: words = ["abcd","bnrt","crmy","dtye"]

• Validate: 4 × 4, ✓.
• Transpose:
• Col 0: "abcd" → "abcd".
• Col 1: "bnrt" → "bnrt".
• Col 2: "crmy" → "crmy".
• Col 3: "dtye" → "dtye".
• Compare: All match.
• Result: True.

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

• Transpose:
• Col 0: "ball" → "baal".
• Col 1: "area" → "arel".
• Col 2: "lead" → "lead".
• Col 3: "lady" → "lady".
• Compare: "ball" ≠ "baal", fail.
• Result: False.

Code for Transposition Approach

Copy codeclass Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        if not words or len(words) != len(words[0]):
            return False
        n = len(words)
        for word in words:
            if len(word) != n:
                return False

        # Build transposed columns
        columns = []
        for c in range(n):
            col = ""
            for r in range(n):
                if c < len(words[r]):
                    col += words[r][c]
                else:
                    col += " "  # Pad if shorter
            columns.append(col.rstrip())  # Remove trailing spaces

        # Compare rows to columns
        for r in range(n):
            if words[r] != columns[r]:
                return False

        return True

• Time Complexity: O(n²)—build and compare n × n.
• Space Complexity: O(n²)—store columns.

It’s a grid-flipping matcher!

Comparing the Two Solutions

• Row-Column Comparison (Best):
• Pros: O(n²), O(1), fast and lean.
• Cons: Direct check less visual.
• Matrix Transposition (Alternative):
• Pros: O(n²), O(n²), explicit flip.
• Cons: More space.

Comparison wins for efficiency.

Additional Examples and Edge Cases

• ["a"]: True.
• ["ab","b"]: True.
• [""]: False (not square).

Comparison handles all.

Complexity Breakdown

• Comparison: Time O(n²), Space O(1).
• Transposition: Time O(n²), Space O(n²).

Comparison’s the champ.

Key Takeaways

• Comparison: Check in place!
• Transposition: Flip it out!
• Squares: Symmetry rules.
• Python Tip: Loops rock—see [Python Basics](/python/basics).

Final Thoughts: Square That Word

LeetCode 422: Valid Word Square in Python is a symmetry-checking adventure. Row-column comparison zips through it, while transposition flips it clear. Want more string fun? Try LeetCode 125: Valid Palindrome or LeetCode 271: Encode and Decode Strings. Ready to check? Head to Solve LeetCode 422 on LeetCode and square those words today!