💬 Discord
Sign In
NeetCode #9LC-422EasyArrays & HashingNC Algo100
← Back to All Problems

#9 · #422 · Valid Word Square(有效的单词方阵)

📌 Problem Statement & Constraints

Given an array of strings words, return true if it forms a valid word square: for every valid index pair (i, j), words[i][j] == words[j][i]. Constraints: 1 <= words.length <= 500, 1 <= words[i].length <= 500; all strings consist of lowercase English letters.

💡 Core Algorithmic Approaches

  1. A word square is simply the transpose condition: the matrix must equal its own transpose.
  2. Iterate i over the rows and j over the characters of words[i].
  3. Two failure modes must be checked: j may exceed the number of rows, and i may exceed the length of words[j]. Either means the shape is not square-symmetric.
  4. If words[j] is long enough, compare the characters. Any mismatch fails immediately.

💻 Benchmark Python3 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])):
                # need words[j][i] to exist and match words[i][j]
                if j >= n or i >= len(words[j]) or words[i][j] != words[j][i]:
                    return False
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters): each character of the input is inspected at most once.
💾 Space Complexity
O(1) extra space -- only loop indices.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking words[i][j] != words[j][i]: this raises IndexError when the shape is ragged, e.g. ["abc", "b"] -- words[1][2] does not exist.
  • Assuming the array is a perfect square: it need not be; the length checks are the whole point of the problem.
  • Building the transpose explicitly: it works and is clearer, but allocates O(total characters) for no reason.