Valid Word Square

How it works

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.

Steps

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.

Complexity

• Time complexity: O(n × 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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        for (int wordNum = 0; wordNum < words.size(); ++wordNum) {
            for (int charPos = 0; charPos < words[wordNum].size(); ++charPos) {
                // charPos (curr 'row' word) is bigger than column word, or
                // wordNum (curr 'column' word) is bigger than row word, or
                // characters at index (wordNum,charPos) and (charPos,wordNum) are not equal.
                if (charPos >= words.size() ||
                    wordNum >= words[charPos].size() ||
                    words[wordNum][charPos] != words[charPos][wordNum]){
                    return false;
                }
            }
        }
        return true;
    }
};