LeetCode 422 - Valid Word Square

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem asks us to determine whether a given list of strings forms a valid word square. A word square is a special arrangement of words such that the kth row and the kth column contain the same sequence of letters for every valid index k. Essentially, if you read the words horizontally as rows and vertically as columns, the letters must match.

The input words is an array of strings, where each string represents a row in the potential word square. The length of words (numRows) does not necessarily equal the length of the strings (numColumns), but the algorithm must ensure that for any k, the kth row and column align. The output is a boolean: true if the words form a valid word square and false otherwise.

The constraints tell us that both the number of words and the length of any word can be up to 500, which implies that a solution must handle up to 500x500 character comparisons efficiently. The input guarantees that all characters are lowercase English letters.

Key edge cases include rows of unequal length, rows shorter than the number of words, or empty strings. These can break naive row-column comparisons if not carefully handled.

Approaches

A brute-force approach would explicitly construct the column strings for every index k and compare them to the corresponding row strings. This works because it directly verifies the definition of a word square, but it requires constructing additional strings and iterating over all characters repeatedly. While correct, it may be inefficient for the largest input sizes.

The optimal approach avoids constructing new strings by comparing characters in-place. For each row i and each character j in that row, we directly compare words[i][j] with words[j][i] if both indices exist. This approach leverages the insight that we only need to verify equality of corresponding characters, not entire strings, which reduces overhead and simplifies the logic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n * m)	Construct each column string and compare with row
Optimal	O(n * m)	O(1)	Compare characters directly without extra storage

Here, n is the number of words and m is the maximum length of a word.

Algorithm Walkthrough

Determine the number of rows numRows as len(words).
Iterate over each row i from 0 to numRows - 1.
For each character index j in row i, check if j is a valid row index (j < numRows) and the length of row j is sufficient (len(words[j]) > i). If either check fails, the word square is invalid, so return false.
Compare the character at words[i][j] with words[j][i]. If they are not equal, the word square is invalid, so return false.
If all comparisons pass, return true.

Why it works: The algorithm ensures that for every character position (i, j), the row and column characters are identical. This property guarantees that each row matches the corresponding column, satisfying the definition of a valid word square.

Python Solution

from typing import List

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        numRows = len(words)
        for i in range(numRows):
            for j in range(len(words[i])):
                if j >= numRows or i >= len(words[j]) or words[i][j] != words[j][i]:
                    return False
        return True

The Python implementation first calculates the number of rows. It iterates through each row and character, performing boundary checks to ensure both the row and column exist. If any character mismatch or out-of-bounds condition occurs, it immediately returns false. Otherwise, after completing all iterations, it returns true.

Go Solution

func validWordSquare(words []string) bool {
    numRows := len(words)
    for i := 0; i < numRows; i++ {
        for j := 0; j < len(words[i]); j++ {
            if j >= numRows || i >= len(words[j]) || words[i][j] != words[j][i] {
                return false
            }
        }
    }
    return true
}

The Go implementation mirrors the Python version. Slices handle variable-length rows naturally, and the boundary checks prevent out-of-range panics. The main difference is explicit indexing and iteration over slices instead of Python’s dynamic for-in loops.

Worked Examples

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

i	j	words[i][j]	words[j][i]	Valid?
0	0	a	a	yes
0	1	b	b	yes
0	2	c	c	yes
0	3	d	d	yes
1	0	b	b	yes
1	1	n	n	yes
...	...	...	...	...

All comparisons match, so the output is true.

Example 2: words = ["ball","area","read","lady"]

At i=2, j=2, words[2][2] = a but words[2][2] = e in the column check, so output is false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	We iterate over each character in each word exactly once.
Space	O(1)	No additional storage beyond loop indices is used.

This is efficient because we do not construct extra strings, only performing character comparisons.

Test Cases

# Basic valid square
assert Solution().validWordSquare(["abcd","bnrt","crmy","dtye"]) == True

# Another valid square with different row lengths
assert Solution().validWordSquare(["abcd","bnrt","crm","dt"]) == True

# Invalid square due to mismatch
assert Solution().validWordSquare(["ball","area","read","lady"]) == False

# Single character valid square
assert Solution().validWordSquare(["a"]) == True

# Two-row mismatch
assert Solution().validWordSquare(["ab","bc"]) == False

# Empty string edge case
assert Solution().validWordSquare([""]) == True

# Different lengths but valid
assert Solution().validWordSquare(["a","b"]) == False

Test	Why
["abcd","bnrt","crmy","dtye"]	Valid 4x4 square
["abcd","bnrt","crm","dt"]	Valid, shorter rows
["ball","area","read","lady"]	Mismatch invalidates square
["a"]	Single-row, trivial valid case
["ab","bc"]	Two-row mismatch
[""]	Single empty row, edge case
["a","b"]	Two different characters, invalid

Edge Cases

Unequal row lengths: If rows have different lengths, accessing words[j][i] could be out of bounds. The solution explicitly checks i < len(words[j]) to prevent this error.

Single row/column: A single-character word or single-row array is a valid square by definition. The algorithm naturally handles this by iterating over available indices.

Empty strings: Rows may contain empty strings, which are edge cases for indexing. The algorithm correctly returns true if all checks pass because no character mismatches exist in such rows.

This careful handling ensures correctness across varied input shapes.