Problem Description

Given a list of strings words, where each string represents a row in a word square, determine if the input forms a valid word square.

A word square is valid if and only if the kth row and kth column read the exact same string for all valid k (0-indexed). In other words, for every position (i, j) in the square, words[i][j] must equal words[j][i] whenever both are defined.

• Each words[i] can have different lengths.
• It is possible for some words[i][j] or words[j][i] to be undefined (if the row or column is too short).
• The function should return true if the square is valid, and false otherwise.

Constraints:

• 1 ≤ words.length ≤ 500
• 1 ≤ words[i].length ≤ 500
• All strings consist of lowercase English letters only.

Thought Process

At first glance, the problem seems to require checking that the input forms a perfect square (same number of rows and columns, and all strings of equal length). However, since each row can have different lengths, we need to be more careful.

The key insight is: for each character at position (i, j) in the 2D grid, it must match the character at position (j, i), if both exist. If either words[i][j] or words[j][i] is missing, the square is not valid.

A brute-force solution would be to loop over every possible (i, j) pair, but that could be inefficient. Instead, we can iterate over the rows and columns up to the maximum length, checking for mismatches or missing characters.

This is similar to checking if a matrix is symmetric along its main diagonal, with the added twist that some rows might be shorter than others.

Solution Approach

We'll validate the word square by comparing each character at position (i, j) with its "transpose" at (j, i). Here's how:

1. Iterate over each row i: For each row, loop through each character j in words[i].
2. Check bounds: For each character words[i][j], ensure that words[j] exists (i.e., j < len(words)) and that words[j][i] exists (i.e., i < len(words[j])).
3. Compare characters: If both characters exist, check if words[i][j] equals words[j][i]. If not, return false.
4. Return true if no mismatches: If all checks pass, return true at the end.

We use direct index checks to avoid index out-of-bounds errors and to ensure that the word square is well-formed.

Example Walkthrough

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

Let's walk through the validation:

• Row 0 ("abcd"):
  • (0,0): 'a' vs (0,0): 'a' — OK
  • (0,1): 'b' vs (1,0): 'b' — OK
  • (0,2): 'c' vs (2,0): 'c' — OK
  • (0,3): 'd' vs (3,0): 'd' — OK
• Row 1 ("bnrt"):
  • (1,0): 'b' vs (0,1): 'b' — OK
  • (1,1): 'n' vs (1,1): 'n' — OK
  • (1,2): 'r' vs (2,1): 'r' — OK
  • (1,3): 't' vs (3,1): 't' — OK
• Row 2 ("crmy"):
  • (2,0): 'c' vs (0,2): 'c' — OK
  • (2,1): 'r' vs (1,2): 'r' — OK
  • (2,2): 'm' vs (2,2): 'm' — OK
  • (2,3): 'y' vs (3,2): 'y' — OK
• Row 3 ("dtye"):
  • (3,0): 'd' vs (0,3): 'd' — OK
  • (3,1): 't' vs (1,3): 't' — OK
  • (3,2): 'y' vs (2,3): 'y' — OK
  • (3,3): 'e' vs (3,3): 'e' — OK

Counter-Example Input:
words = ["ball",
    "area",
    "read",
    "lady"]

• Check (0,1): 'a' vs (1,0): 'a' — OK
• Check (1,2): 'e' vs (2,1): 'e' — OK
• Check (2,3): 'd' vs (3,2): 'd' — OK
• Check (3,0): 'l' vs (0,3): 'l' — OK
• Check (1,3): 'a' vs (3,1): 'a' — OK
• But check (0,2): 'l' vs (2,0): 'r' — Mismatch!

Code Implementation

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

class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < words[i].size(); ++j) {
                if (j >= n || i >= words[j].size() || words[i][j] != words[j][i])
                    return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean validWordSquare(List<String> words) {
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            String row = words.get(i);
            for (int j = 0; j < row.length(); ++j) {
                if (j >= n || i >= words.get(j).length() || row.charAt(j) != words.get(j).charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}
      

var validWordSquare = function(words) {
    let n = words.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < words[i].length; j++) {
            if (j >= n || i >= words[j].length || words[i][j] !== words[j][i]) {
                return false;
            }
        }
    }
    return true;
};
      

Time and Space Complexity

• Brute-force approach:
  • If you naively checked every possible (i, j) in a full 2D grid of size N x M, time complexity could be up to O(N * M), where N is the number of rows and M is the maximum row length.
• Optimized approach (current solution):
  • We only check existing characters in each row, so the total number of checks is proportional to the total number of characters: O(total_characters). In the worst case (all rows are length N), this is O(N^2).
  • Space complexity is O(1), since we use only a few variables for indexing and comparison.

The solution is efficient because it avoids unnecessary checks and does not use extra memory for data structures.

Summary

The Valid Word Square problem is a neat exercise in matrix symmetry and careful index handling. By iterating over each character and checking its "transpose" counterpart, we ensure that the word square property holds. The solution is both simple and robust, handling cases where rows may be of different lengths and ensuring no out-of-bounds errors. The approach is optimal in both time and space, making it a great example of clean, efficient coding.