How hard is LeetCode 422. Valid Word Square?

LeetCode 422. Valid Word Square is rated Easy on LeetCode.

What is the time complexity of LeetCode 422. Valid Word Square?

The Python solution on this page runs in O(n^2), where n is the length of `words`.

What is the space complexity of LeetCode 422. Valid Word Square?

The Python solution on this page uses $O(1)` auxiliary space.

What topics does LeetCode 422. Valid Word Square cover?

LeetCode 422. Valid Word Square is tagged Array and Matrix on LeetCode.

Is LeetCode 422. Valid Word Square a premium problem?

Yes. LeetCode 422. Valid Word Square is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Valid Word Square — LeetCode 422 Python Solution

EasyLeetCode PremiumArrayMatrix

Problem: #422
Pattern: Matrix and Grid
Reading time: 2 min
Source: leetcode.com

The problem

Given an array of strings words, return true if it forms a valid word square. A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).

Example

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation: The 1st row and 1st column both read "abcd".

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n^2), where n is the length of `words`
Space	$O(1)` auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 422. Valid Word Square is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 422. Valid Word Square?: LeetCode 422. Valid Word Square is rated Easy on LeetCode.
What is the time complexity of LeetCode 422. Valid Word Square?: The Python solution on this page runs in O(n^2), where n is the length of `words`.
What is the space complexity of LeetCode 422. Valid Word Square?: The Python solution on this page uses $O(1)` auxiliary space.
What topics does LeetCode 422. Valid Word Square cover?: LeetCode 422. Valid Word Square is tagged Array and Matrix on LeetCode.
Is LeetCode 422. Valid Word Square a premium problem?: Yes. LeetCode 422. Valid Word Square is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.