Problem Description

You are given an array of strings words. Your task is to determine if these strings form a valid word square.

A word square is formed when the strings are arranged as a square grid where:

• The k-th row reads the same as the k-th column
• This must be true for all valid indices k where 0 <= k < max(numRows, numColumns)

In other words, if you write the words one below another to form a grid, reading horizontally (left to right) at position k should give you the exact same string as reading vertically (top to bottom) at position k.

For example, if we have words ["abcd", "bnrt", "crmy", "dtye"], they form a valid word square because:

• Row 0: "abcd", Column 0: "abcd" (reading first character of each word)
• Row 1: "bnrt", Column 1: "bnrt" (reading second character of each word)
• Row 2: "crmy", Column 2: "crmy" (reading third character of each word)
• Row 3: "dtye", Column 3: "dtye" (reading fourth character of each word)

The solution checks this by iterating through each character position (i, j) in the words array. For each character at words[i][j], it verifies that:

1. The corresponding position words[j][i] exists (not out of bounds)
2. The characters match: words[i][j] == words[j][i]

If any position violates these conditions, the function returns false. If all positions satisfy the word square property, it returns true.

Intuition

The key insight is recognizing that a word square is essentially checking if a matrix is symmetric along its main diagonal. When we arrange the words as rows in a grid, each character at position (i, j) must equal the character at position (j, i).

Think of it like looking at a mirror reflection across the diagonal - what appears in row i, column j must be exactly the same as what appears in row j, column i.

We arrive at this approach by understanding that:

1. Each word represents a row in our conceptual grid
2. The j-th character of the i-th word is at position (i, j) in this grid
3. For a valid word square, this character must match the i-th character of the j-th word (position (j, i))

The challenge is that our "grid" might not be a perfect square - words can have different lengths, and we might have different numbers of words than characters in each word. This means we need to be careful about boundary checking.

When checking words[i][j], we must ensure:

• j < len(words) - the column index j must correspond to an existing word
• i < len(words[j]) - the row index i must be within the length of word at position j
• If either condition fails, we're trying to compare with a non-existent character, so it can't form a valid word square

This leads us to iterate through each character of each word and verify the symmetry property while handling the boundary cases. If we find any mismatch or out-of-bounds access, we immediately know it's not a valid word square.

Solution Approach

The solution uses a straightforward iterative approach to verify the word square property. Let's walk through the implementation step by step:

1. Get the number of words: We store m = len(words) to know how many words (rows) we have in our array.

2. Iterate through each word with its index: We use enumerate(words) to get both the word and its row index i.

3. For each character in the current word: We iterate through each character c at position j in word i. This represents checking element at position (i, j) in our conceptual grid.

4. Perform three critical checks for each character position (i, j):

   • Column bounds check: j >= m - If the column index j exceeds the number of words, then words[j] doesn't exist, so we can't form a valid square.
   • Row bounds check: i >= len(words[j]) - If we try to access words[j][i] but word j doesn't have enough characters (its length is less than or equal to i), the position is out of bounds.
   • Character match check: c != words[j][i] - The actual comparison to verify if the character at (i, j) matches the character at (j, i).

5. Early termination: If any of these three conditions are true, we immediately return False as the word square property is violated.

6. Success case: If we complete all iterations without finding any violations, we return True.

The algorithm has a time complexity of O(n × m) where n is the number of words and m is the maximum length of any word, as we potentially check each character once. The space complexity is O(1) as we only use a constant amount of extra space for variables.

This approach efficiently validates the symmetric property required for a word square while handling the edge cases of non-square grids formed by words of varying lengths.

Example Walkthrough

Let's walk through a small example with words = ["ball", "area", "lead", "lady"].

First, let's visualize this as a grid:

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

Now we'll check if this forms a valid word square by verifying that each row matches its corresponding column.

Step 1: Check word 0 ("ball")

• Position (0,0): 'b' should equal words[0][0] = 'b' ✓
• Position (0,1): 'a' should equal words[1][0] = 'a' ✓
• Position (0,2): 'l' should equal words[2][0] = 'l' ✓
• Position (0,3): 'l' should equal words[3][0] = 'l' ✓

Step 2: Check word 1 ("area")

• Position (1,0): 'a' should equal words[0][1] = 'a' ✓
• Position (1,1): 'r' should equal words[1][1] = 'r' ✓
• Position (1,2): 'e' should equal words[2][1] = 'e' ✓
• Position (1,3): 'a' should equal words[3][1] = 'a' ✓

Step 3: Check word 2 ("lead")

• Position (2,0): 'l' should equal words[0][2] = 'l' ✓
• Position (2,1): 'e' should equal words[1][2] = 'e' ✓
• Position (2,2): 'a' should equal words[2][2] = 'a' ✓
• Position (2,3): 'd' should equal words[3][2] = 'd' ✓

Step 4: Check word 3 ("lady")

• Position (3,0): 'l' should equal words[0][3] = 'l' ✓
• Position (3,1): 'a' should equal words[1][3] = 'a' ✓
• Position (3,2): 'd' should equal words[2][3] = 'd' ✓
• Position (3,3): 'y' should equal words[3][3] = 'y' ✓

All checks pass! This forms a valid word square because:

• Row 0 "ball" = Column 0 "ball" (reading b,a,l,l vertically)
• Row 1 "area" = Column 1 "area" (reading a,r,e,a vertically)
• Row 2 "lead" = Column 2 "lead" (reading l,e,a,d vertically)
• Row 3 "lady" = Column 3 "lady" (reading l,a,d,y vertically)

Counter-example: If we had words = ["abc", "bde", "cef"], this would fail at position (0,2) because we'd need words[2][0] but "cef" starts with 'c', not matching the 'c' at position (0,2) in "abc".

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the total number of characters across all words. This can also be expressed as O(m × k) where m is the number of words and k is the maximum length of any word. In the worst case where we have a valid word square with m words each of length m, the complexity becomes O(m²). The algorithm iterates through each character in each word exactly once, and for each character, it performs constant-time operations (index checking and character comparison).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the loop variables i, j, w, and c, regardless of the input size. No additional data structures are created that scale with the input.

Common Pitfalls

1. Assuming Square Matrix Without Validation

One of the most common mistakes is assuming that the input forms a perfect square matrix (n×n grid) where all words have the same length equal to the number of words. This leads to index out of bounds errors when words have different lengths.

Incorrect Approach:

def validWordSquare(self, words: List[str]) -> bool:
    n = len(words)
    for i in range(n):
        for j in range(n):  # Assumes all words have length n
            if words[i][j] != words[j][i]:  # Can crash here!
                return False
    return True

Why it fails: If words = ["abc", "b"], accessing words[1][1] or words[1][2] will cause an IndexError.

2. Incorrect Order of Boundary Checks

Another pitfall is checking character equality before verifying bounds, which can lead to runtime errors.

Incorrect Approach:

def validWordSquare(self, words: List[str]) -> bool:
    for i, word in enumerate(words):
        for j, c in enumerate(word):
            # Checking character match before bounds - WRONG!
            if c != words[j][i]:  # Can crash if words[j] doesn't exist
                return False
            if j >= len(words) or i >= len(words[j]):
                return False
    return True

3. Missing Asymmetric Length Validation

Some implementations forget to check if the transpose position exists when the matrix is not square.

Incorrect Approach:

def validWordSquare(self, words: List[str]) -> bool:
    for i in range(len(words)):
        word = words[i]
        for j in range(len(word)):
            # Only checking if words[j] exists, not if words[j][i] exists
            if j < len(words) and word[j] != words[j][i]:
                return False
    return True

Solution to Avoid These Pitfalls:

The correct approach must:

1. Check column bounds first (j >= num_words)
2. Then check row bounds (i >= len(words[j]))
3. Only then perform character comparison (char != words[j][i])

This order ensures we never access an invalid index. The key insight is treating the word array as a potentially non-square, ragged 2D array where careful boundary checking is essential before any character access.