We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Word Square

Number: 422

Difficulty: Easy

Paid? Yes

Companies: Apple, Google

Problem Description

Given an array of strings words, determine if they form a valid word square. A valid word square means that for every k (0 <= k < max(numRows, numColumns)), the k-th row and k-th column read the same string.

Key Insights

  • The k-th row should be equal to the k-th column.
  • Not every word is the same length; checks must be performed within bounds.
  • Iterating over each character and cross-verifying with the corresponding column character is sufficient.

Space and Time Complexity

Time Complexity: O(N * L) where N is the number of words and L is the average length of the words. Space Complexity: O(1) additional space is used for the checking procedure.

Solution

We iterate through each word (row) and each character (column) in the word. For every character at position (i, j), we confirm that there is a corresponding word at index j and that its length is greater than i. Then we check that the character at position (j, i) in that word is the same as the current character. If any of these checks fail, we return false. If all checks pass, the words form a valid word square.

Code Solutions

# Function to check if the provided words form a valid word square
def validWordSquare(words):
    # Iterate over each row with its index
    for i in range(len(words)):
        # Iterate over each character in the current row
        for j in range(len(words[i])):
            # Check if the corresponding column exists
            if j >= len(words) or i >= len(words[j]) or words[i][j] != words[j][i]:
                return False
    return True

# Example test case
words = ["abcd","bnrt","crmy","dtye"]
print(validWordSquare(words))  # Expected output: True
← Back to All Questions