Valid Word Square

Easy

Asked by:

36 views

Topics:

ArraysStrings

Given an n x n square matrix of words, check if it is a valid word square. That is, the k^th row and column read the exact same string, where 0 ≤ k < n.

For example, the word square

["ball",
 "area",
 "lead",
 "lady"]

is a valid word square because each word reads the same both horizontally and vertically.

Example 1:

Input: words = ["ball","area","lead","lady"]
Output: true
Explanation:
The 1st row and 1st column both read "ball".
The 2nd row and 2nd column both read "area".
The 3rd row and 3rd column both read "lead".
The 4th row and 4th column both read "lady".

Example 2:

Input: words = ["abat","baba","atan","atal"]
Output: false
Explanation:
The 1st row and 1st column both read "abat".
The 2nd row and 2nd column both read "baba".
The 3rd row and 3rd column read "atan" != "tana".
The 4th row and 4th column read "atal" != "lata".

Constraints:

1 <= words.length <= 500
words[i].length <= 500
1 <= words[i].length <= 500
words[i] consists of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the word list and the length of each word? Are we expecting extremely large inputs?
Can the input word list contain empty strings, null values, or words with different lengths?
Are the input words guaranteed to contain only lowercase English letters, or can they contain other characters?
If the input is not a valid word square, should I return a specific error code or throw an exception, or simply return false?
Is it possible for a valid word square to have only one word? Or must it have at least two?

Brute Force Solution

Approach

The brute force strategy to determine if a list of words forms a valid word square is about checking *every* single possibility. We want to see if the word at row 'r' is the same as the word at column 'r'. If we examine every word in this way, we can definitively say if the arrangement is a valid square.

Here's how the algorithm would work step-by-step:

First, take the first word in the list. Compare its letters with the letters of all the other words, comparing each letter to what *should* be in the corresponding position if it were a valid square.
If any of these comparisons don't match up, immediately say it's NOT a valid square.
If the first word matches, move on to the second word, and do the same comparison with all other words. Again, we want to see if the letters match up as if they were a word square.
Keep repeating this process for every word in the list. If any comparison fails at any point, it's NOT a valid square.
If you manage to compare *every* word with all others and *all* comparisons are successful, then you can say with certainty that it IS a valid word square.

Code Implementation

def is_valid_word_square(words):
    number_of_words = len(words)

    for row_index in range(number_of_words):
        word = words[row_index]
        word_length = len(word)

        # Iterate through each letter in the current word
        for column_index in range(word_length):
            # Check if the column index is within the bounds of other words
            if column_index >= number_of_words:
                return False

            other_word = words[column_index]

            # Check if the row index is within the bounds of the other word
            if row_index >= len(other_word):
                return False

            # Compare the letter at (row, col) with the letter at (col, row)
            if word[column_index] != other_word[row_index]:
                return False

    # If all checks pass, it's a valid word square
    return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each word in the input list of words, where n is the number of words. For each word, it compares its characters with the corresponding characters in other words to validate the word square condition. In the worst case, for each of the n words, we need to potentially check each of the other n words, leading to a nested loop structure. Therefore, the time complexity is proportional to n * n which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm operates directly on the input list of words without creating any auxiliary data structures like temporary lists, arrays, or hash maps. It primarily involves comparisons using index variables to traverse the input. Therefore, the space used remains constant and independent of the number of words, N, or their lengths. This results in an auxiliary space complexity of O(1).

Optimal Solution

Approach

The core idea is to check if the word arrangement is symmetric. We simply compare words in the rows to the words in the columns to ensure they match, indicating a valid word square.

Here's how the algorithm would work step-by-step:

Imagine the words are arranged to form a grid.
Check if the first word in the first row is the same as the first word in the first column.
Continue this pattern: the second word in the first row should be the same as the second word in the first column, and so on.
Repeat this comparison for all rows and columns. If any mismatch is found, the word arrangement is invalid.
If all the words in the rows match the words in the corresponding columns, then you have a valid word square.

Code Implementation

def is_valid_word_square(words):
    word_count = len(words)
    for row_index in range(word_count):
        word_length = len(words[row_index])

        #Check if dimensions are not square
        if word_length != word_count:
            return False

        for column_index in range(word_length):

            # Check for out-of-bounds access
            if column_index >= word_count or row_index >= len(words[column_index]):
                return False

            #This ensures we don't compare past the length of the column word
            if column_index >= len(words[row_index]) or row_index >= len(words[column_index]):
                return False

            #Crucial step: Compare row and column chars for symmetry
            if words[row_index][column_index] != words[column_index][row_index]:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of words and m be the maximum length of a word in the input list. The algorithm iterates through each word (row) and compares its characters with the characters in the corresponding column. For each of the n words, it iterates up to the length of that word, which is bounded by m. Therefore, the time complexity is determined by the number of these character comparisons which is proportional to n*m. If we assume that the words' lengths are roughly the same, we can express this as O(n*m).

Space Complexity

O(1) – The algorithm described compares words in rows to words in columns using index comparisons. It does not create any auxiliary data structures such as temporary lists, hash maps, or recursion stacks to store intermediate results or track visited locations. Only index variables are used for iterating which takes constant space, irrespective of the input size N, where N is the number of words in the input list. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return true immediately as an empty square is considered valid.
Array with only one string	Check if the single string's length is 1 and if the string's character at index 0 matches itself.
Array with strings of varying lengths	Return false because a valid word square requires all strings to be of the same length.
String contains non-alphabetic characters	The solution should handle non-alphabetic characters, either by throwing an error or ignoring them depending on requirements.
Input forms a square but fails validation in the middle	The validation should continue until the failure condition is identified, then return false.
Strings with different casing	Convert all strings to either lowercase or uppercase before processing to ensure case-insensitive validation.
Very long strings that might cause performance issues	The solution has O(n^2) complexity where n is the square size, so long strings won't cause issues, just longer execution time.
Valid square with identical characters	The solution correctly handles this by comparing characters at corresponding indices.

Null or empty input array

How to Handle:

Return true immediately as an empty square is considered valid.

Array with only one string

How to Handle:

Check if the single string's length is 1 and if the string's character at index 0 matches itself.

Array with strings of varying lengths

How to Handle:

Return false because a valid word square requires all strings to be of the same length.

String contains non-alphabetic characters

How to Handle:

The solution should handle non-alphabetic characters, either by throwing an error or ignoring them depending on requirements.

Input forms a square but fails validation in the middle

How to Handle:

The validation should continue until the failure condition is identified, then return false.

Strings with different casing

How to Handle:

Convert all strings to either lowercase or uppercase before processing to ensure case-insensitive validation.

Very long strings that might cause performance issues

How to Handle:

The solution has O(n^2) complexity where n is the square size, so long strings won't cause issues, just longer execution time.

Valid square with identical characters

How to Handle:

The solution correctly handles this by comparing characters at corresponding indices.