# LeetCode 422: Valid Word Square

## Problem Restatement

We are given an array of strings:

```python
words
```

Return `True` if the strings form a valid word square.

A word square means:

```python
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 `k`th row and `k`th 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

| Item | Meaning |
|---|---|
| Input | A list of strings `words` |
| Output | `True` if it forms a valid word square |
| Row | `words[i]` |
| Column | Characters `words[0][i]`, `words[1][i]`, ... where they exist |
| Important issue | Words may have different lengths |

Example function shape:

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

## Examples

Example 1:

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

The answer is:

```python
True
```

Rows:

```text
abcd
bnrt
crmy
dtye
```

Columns:

```text
abcd
bnrt
crmy
dtye
```

Every row matches the corresponding column.

Example 2:

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

The answer is:

```python
True
```

The rows are:

```text
abcd
bnrt
crm
dt
```

The columns are:

```text
abcd
bnrt
crm
dt
```

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

Example 3:

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

The answer is:

```python
False
```

The third row is:

```python
"read"
```

but the third column is:

```python
"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:

```python
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:

```python
words[i][j]
```

there must be a matching character at the transposed position:

```python
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 `i`th row and the `i`th 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

| Metric | Value | Why |
|---|---|---|
| Time | `O(T)` | We check each character once |
| Space | `O(1)` | Only loop indices are used |

Here:

| Symbol | Meaning |
|---|---|
| `T` | Total number of characters in all words |

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

```python
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:

```python
for i, word in enumerate(words):
```

Here `i` is the row index.

Then we scan each character inside that row:

```python
for j, ch in enumerate(word):
```

Here `j` is the column index.

The character `ch` is:

```python
words[i][j]
```

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

```python
if j >= len(words):
    return False
```

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

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

Finally, we compare the two transposed characters:

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

If no check fails, the square is valid:

```python
return True
```

## Testing

```python
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

| Test | Why |
|---|---|
| Full square | Standard valid case |
| Ragged valid square | Words have different lengths but still match |
| Mismatch | Same size but different row and column |
| Missing transposed character | Detects too-short row |
| Single word | Minimum valid input |
| `["ab", "ba"]` | Small symmetric square |
| `["ab", "b"]` | Small ragged valid square |
| Unequal transposed character | Detects character mismatch |