1. Storing New Words

Intuition

A word square has a special property: the k-th row reads the same as the k-th column. To verify this, we can construct new words by reading each column vertically and then compare them to the original row words. If every row word matches its corresponding column word, we have a valid word square. We first check basic constraints: the number of rows must equal the maximum word length, and the first row must be the longest.

Algorithm

1. Count the number of rows and find the maximum column length.
2. If the first row is not the longest or the number of rows does not equal the number of columns, return false.
3. For each column index col, build a new word by collecting characters from each row at that column position (skip if the row is too short).
4. Store all these column words in a list.
5. Compare the original words list with the new column words list. Return true if they are identical.

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        cols = 0
        rows = len(words)
        new_words = []
        
        for word in words:
            cols = max(cols, len(word))

        # If the first row doesn't have maximum number of characters, or
        # the number of rows is not equal to columns it can't form a square.
        if cols != len(words[0]) or rows != cols:
            return False

        for col in range(cols):
            new_word = []
            # Iterate on each character of column 'col'.
            for row in range(rows):
                # If the current row's word's size is less than the column number it means this column is empty,
                # or, if there is a character present then use it to make the new word.
                if col < len(words[row]):
                    new_word.append(words[row][col])
            # Push the new word of column 'col' in the list.
            new_words.append(''.join(new_word))

        # Check if all row's words match with the respective column's words.
        return words == new_words

Time & Space Complexity

• Time complexity: $O(n \cdot m)$
• Space complexity: $O(n \cdot m)$

Where $n$ is the number of strings in the words array and $m$ is the maximum length of a string

---

2. Iterate on the Matrix

Intuition

Instead of building new words and comparing lists, we can directly verify the word square property: for every position (row, col), the character must equal the character at position (col, row). This is essentially checking that the matrix is symmetric along its main diagonal. We iterate through each character and verify this symmetry, handling cases where one position might be out of bounds.

Algorithm

1. For each word at index wordNum:
   • For each character position charPos in that word:
     • Check if position (charPos, wordNum) is valid (charPos < number of words, wordNum < length of words[charPos]).
     • If invalid, return false.
     • If words[wordNum][charPos] != words[charPos][wordNum], return false.
2. If all checks pass, return true.

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        for word_num in range(len(words)):
            for char_pos in range(len(words[word_num])):
                # char_pos (curr 'row' word) is bigger than column word, or
                # word_num (curr 'column' word) is bigger than row word, or 
                # characters at index (word_num,char_pos) and (char_pos,word_num) are not equal.
                if char_pos >= len(words) or \
                    word_num >= len(words[char_pos]) or \
                    words[word_num][char_pos] != words[char_pos][word_num]:
                    return False
        return True

Time & Space Complexity

• Time complexity: $O(n \cdot m)$
• Space complexity: $O(1)$ constant space

Where $n$ is the number of strings in the words array and $m$ is the maximum length of a string

---

Common Pitfalls

Not Handling Jagged Arrays Correctly

Words in the input can have different lengths, creating a jagged grid. When checking if words[i][j] == words[j][i], you must first verify that both positions exist. If words[j] does not have a character at index i (because it is shorter), or if j exceeds the number of words, the comparison is invalid. Always check bounds before accessing characters.

Assuming Square Dimensions

Do not assume that the number of rows equals the maximum word length. For example, ["abc", "de"] has 2 rows but the first word has 3 characters. A valid word square requires the k-th row to match the k-th column exactly, which implicitly requires consistent dimensions. Verify that accessing words[charPos][wordNum] is valid before comparing.