422. Valid Word Square
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 38.2%
Problem Breakdown
The problem asks us to determine whether a given sequence of words forms a valid word square. A sequence of words forms a valid word square if the kth row and column read the exact same string for all 0 ≤ k < max(numRows, numColumns). The input is a list of strings where each string represents a word. The output should be a boolean indicating whether the sequence forms a valid word square.
Inputs:
- A list of strings (
words), where each string contains only lowercase English letters.
Outputs:
- A boolean value (
trueorfalse) indicating whether the input forms a valid word square.
Implicit Constraints and Edge Cases:
- The number of words is between 1 and 500.
- Each word length is between 1 and 500.
- Words contain only lowercase English letters.
- Handle cases where rows and columns have different lengths.
- Handle cases where the input list is empty or contains only one word.
Intuition
The brute-force approach would involve checking each row against its corresponding column for equality. This approach would be inefficient because it requires iterating over all characters in the words, leading to a time complexity of O(n^2), where n is the maximum length of the words.
A better approach involves leveraging the properties of word squares. Specifically, for a valid word square, the length of each row should not exceed the number of rows, and similarly, the length of each column should not exceed the number of columns. This insight allows us to avoid unnecessary comparisons and reduce the time complexity.
Approach
- Check Row Lengths: Ensure that no row exceeds the total number of words.
- Check Column Lengths: For each word, ensure that its characters match the corresponding characters in other words up to the length of the current word.
- Iterate and Compare: Iterate through each word and compare it with the corresponding column values.
Complexity Analysis
- Time Complexity: O(n^2), where n is the maximum length of the words. This is because we need to check each character in the words.
- Space Complexity: O(1), as we are not using any additional data structures that grow with input size.
Solution
def validWordSquare(words):
# Check if each row's length does not exceed the number of rows
for i, word in enumerate(words):
if len(word) > len(words):
return False
# Check each character in the words against the corresponding column characters
for i in range(len(words)):
for j in range(len(words[i])):
if j >= len(words) or i >= len(words[j]) or words[i][j] != words[j][i]:
return False
return True
# Example usage:
words1 = ["abcd", "bnrt", "crmy", "dtye"]
words2 = ["abcd", "bnrt", "crm", "dt"]
words3 = ["ball", "area", "read", "lady"]
print(validWordSquare(words1)) # Output: True
print(validWordSquare(words2)) # Output: True
print(validWordSquare(words3)) # Output: False
Edge Cases Handled
- Empty Input: The function handles an empty input list by returning
Truesince there are no rows or columns to compare. - Single Word: If the input contains only one word, it is trivially a valid word square.
- Rows and Columns of Different Lengths: The function checks that each row does not exceed the number of words and compares characters up to the length of the current word, ensuring correct handling of different lengths.