LeetCode 422: Valid Word Square

Problem Restatement

We are given an array of strings:

words

Return True if the strings form a valid word square.

A word square means:

row k == column k

for every valid index k.

The words may have different lengths, so we must be careful with missing characters.

The source statement defines a valid word square as a sequence where the kth row and kth column read the same string, for 0 <= k < max(numRows, numColumns). The constraints are 1 <= words.length <= 500, 1 <= words[i].length <= 500, and each word contains lowercase English letters.

Input and Output

Example function shape:

def validWordSquare(words: list[str]) -> bool:
    ...

Examples

Example 1:

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

The answer is:

True

Rows:

abcd
bnrt
crmy
dtye

Columns:

abcd
bnrt
crmy
dtye

Every row matches the corresponding column.

Example 2:

words = ["abcd", "bnrt", "crm", "dt"]

The answer is:

True

The rows are:

abcd
bnrt
crm
dt

The columns are:

abcd
bnrt
crm
dt

Even though the words have different lengths, the row and column strings still match.

Example 3:

words = ["ball", "area", "read", "lady"]

The answer is:

False

The third row is:

"read"

but the third column is:

"lead"

They do not match.

First Thought: Build the Columns

One direct approach is to construct every column string.

For each column index c, collect:

words[0][c], words[1][c], words[2][c], ...

when those characters exist.

Then compare each column string with words[c].

This works, but building column strings uses extra memory.

We can check the same condition directly with indices.

Key Insight

The word square condition is the same as matrix symmetry.

For every character at position:

words[i][j]

there must be a matching character at the transposed position:

words[j][i]

So for every existing words[i][j], we must verify:

1. Row j exists.
2. Column position i exists inside words[j].
3. The characters are equal.

If any of these checks fails, the word square is invalid.

Algorithm

Loop through every row index i.

Loop through every character index j in words[i].

For each character words[i][j]:

1. If j >= len(words), return False.
2. If i >= len(words[j]), return False.
3. If words[i][j] != words[j][i], return False.

If all checks pass, return True.

Correctness

A valid word square requires the ith row and the ith column to read the same string.

That means every character in row i, column j, must match the character in row j, column i.

The algorithm checks exactly this condition for every existing character words[i][j].

If the transposed position does not exist, then the corresponding column is too short or the required row does not exist. In that case, the row and column cannot be equal, so returning False is correct.

If the transposed character exists but differs, then the corresponding row and column read different strings, so returning False is correct.

If the algorithm finishes without finding any missing or mismatched transposed character, then every row-character has a matching column-character. Therefore, every row equals its corresponding column, and the word square is valid.

Complexity

Here:

Since there can be up to 500 words and each word can have length up to 500, the worst-case time is O(500 * 500).

Implementation

from typing import List

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        for i, word in enumerate(words):
            for j, ch in enumerate(word):
                if j >= len(words):
                    return False

                if i >= len(words[j]):
                    return False

                if ch != words[j][i]:
                    return False

        return True

Code Explanation

We scan each row:

for i, word in enumerate(words):

Here i is the row index.

Then we scan each character inside that row:

for j, ch in enumerate(word):

Here j is the column index.

The character ch is:

words[i][j]

Before comparing it with words[j][i], we check that row j exists:

if j >= len(words):
    return False

Then we check that words[j] is long enough:

if i >= len(words[j]):
    return False

Finally, we compare the two transposed characters:

if ch != words[j][i]:
    return False

If no check fails, the square is valid:

return True

Testing

def test_valid_word_square():
    s = Solution()

    assert s.validWordSquare(["abcd", "bnrt", "crmy", "dtye"]) is True

    assert s.validWordSquare(["abcd", "bnrt", "crm", "dt"]) is True

    assert s.validWordSquare(["ball", "area", "read", "lady"]) is False

    assert s.validWordSquare(["abc", "b"]) is False

    assert s.validWordSquare(["a"]) is True

    assert s.validWordSquare(["ab", "ba"]) is True

    assert s.validWordSquare(["ab", "b"]) is True

    assert s.validWordSquare(["abc", "bde", "ce"]) is False

    print("all tests passed")

Test Notes