422. Valid Word Square

EasyArrayMatrix

Problem Description

A word square is a sequence of strings arranged in a square grid where the string at each row is the same as the string at each column if both are read from left to right or top to bottom. The kth row and column are considered the same if their characters match for all the indexes from 0 to k. The task is to check whether the given array of strings, words, can form such a valid word square.

Intuition

The intuitive approach to solving this problem is to simulate the process of reading the strings along the rows and columns and ensuring they match. To accomplish this, iterate through each word and character in the array of strings, simultaneously checking the corresponding character in the column. If the index we are checking exceeds either the number of words (for column validation) or the length of the corresponding word (for row length), or if the characters do not match, the array does not form a valid word square, and we return false. If no mismatches are found throughout the iteration, we can conclude that the words form a valid word square, and therefore return true.

This approach relies on the early termination of the validation process as soon as an inconsistency is detected, making it an efficient solution since it doesn't require extra space and minimizes unnecessary computations.

Solution Approach

The solution applies a straightforward algorithm, iterating through each word and its characters in the given words list using a nested loop. The outer loop keeps track of rows and the inner loop keeps track of columns in the would-be word square grid.

For each character c at position (i, j) in the row i (where i is the index of the word in the list and j is the character index in the word), we want to confirm if there is a corresponding character at the position (j, i) of the column j that matches c.

Several key checks are performed for early detection of an invalid word square:

Index Check for Columns: if j >= m, ensures that there isn't an attempt to access a column outside of the words list bounds. For a valid word square, the number of rows and columns should be the same (m).
Index Check for Row Lengths: if i >= len(words[j]), ensures the character at (i, j) does not exceed the length of the word that is supposed to appear in column j, which would render the square invalid.
Character Matching Check: if c != words[j][i], verifies that the character at (i, j) matches the corresponding character at (j, i), following the rule for word square validation.

If any of the above checks fail, the function immediately returns False, indicating that the words do not form a valid word square.

Otherwise, if all characters match properly based on their corresponding rows and columns, and no index out-of-range conditions are encountered, the whole nested loop will complete successfully. After the loops conclude without encountering an inconsistency, the method returns True, indicating that the words represent a valid word square.

The code implementation is efficient, as it only requires a simple check of each character's position in the grid relative to the other words, and thus it operates in O(n^2) time complexity on average, where n is the length of the longest word. This is because each character in each word is being compared once. The space complexity is O(1) since no additional data structures are used beyond the input list itself.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's understand the solution approach using a small example. Consider the array of strings, words = ["AREA","BALL","DEAR","LADY"]. We want to find out if these words can form a valid word square. Below is a step-by-step walk-through of the solution algorithm:

Start with the first word "AREA". Initialize i = 0 for the first row.
- Examine "AREA" for each character j from 0 to 3 (since "AREA" has 4 letters).
- For j = 0, check if words[0][0] ('A') equals words[0][0] ('A'). They match. Continue.
- For j = 1, check if words[0][1] ('R') equals words[1][0] ('B'). They do not match. This means it cannot form a valid word square. Return False.

Using the above example, the algorithm will find a mismatch at the second character of the first word. The character 'R' in row 0 doesn't match the character 'B' in column 0 of the word "BALL". Hence, as per the character matching check, we conclude that the given words cannot form a valid word square, and the algorithm will return False.

If instead, the array were words = ["BALL","AREA","LEAD","LADY"], the checking would proceed as follows:

Start with the first word "BALL". Proceed with character checks:
- words[0][0] ('B') equals words[0][0] ('B').
- words[0][1] ('A') equals words[1][0] ('A').
- words[0][2] ('L') equals words[2][0] ('L').
- words[0][3] ('L') equals words[3][0] ('L').
Move to the second word "AREA" (i = 1).
- words[1][0] ('A') equals words[0][1] ('A').
- words[1][1] ('R') equals words[1][1] ('R').
- words[1][2] ('E') equals words[2][1] ('E').
- words[1][3] ('A') equals words[3][1] ('A').
Continue with "LEAD" (i = 2).
- words[2][0] ('L') equals words[0][2] ('L').
- words[2][1] ('E') equals words[1][2] ('E').
- words[2][2] ('A') equals words[2][2] ('A').
- words[2][3] ('D') equals words[3][2] ('D').
Finally, check "LADY" (i = 3).
- words[3][0] ('L') equals words[0][3] ('L').
- words[3][1] ('A') equals words[1][3] ('A').
- words[3][2] ('D') equals words[2][3] ('D').
- words[3][3] ('Y') equals words[3][3] ('Y').

No inconsistencies are found, and all characters match both horizontally and vertically. Hence, this set of words can form a valid word square, and the algorithm would return True.

Solution Implementation

1class Solution:
2    def validWordSquare(self, words: List[str]) -> bool:
3        # Get the number of words, which corresponds to the square's dimension
4        num_words = len(words)
5      
6        # Loop through each word in the list
7        for row, word in enumerate(words):
8            # Loop through each character in the current word
9            for col, char in enumerate(word):
10                # Check if the current column is >= the number of words
11                # Or if the current row is >= the length of the word at the current column index
12                # Or if the character doesn't match the transposed character (symmetry check)
13                if col >= num_words or row >= len(words[col]) or char != words[col][row]:
14                    return False
15        # If no mismatch was found, return True indicating the words form a valid word square
16        return True
17
18# Example of how to use it:
19# sol = Solution()
20# result = sol.validWordSquare(["abcd", "bnrt", "crm", "dt"])
21# print(result) # Should output True if it's a valid word square or False otherwise
22

1class Solution {
2    public boolean validWordSquare(List<String> words) {
3        // Get the number of words in the list
4        int numRows = words.size();
5      
6        // Iterate over each word in the list
7        for (int rowIndex = 0; rowIndex < numRows; ++rowIndex) {
8            int numCharsInRow = words.get(rowIndex).length();
9          
10            // Iterate over each character in the current word
11            for (int colIndex = 0; colIndex < numCharsInRow; ++colIndex) {
12                // Check if the current column index is outside the number of rows
13                // or if the row index is outside the length of the word at the current column index
14                if (colIndex >= numRows || rowIndex >= words.get(colIndex).length()) {
15                    return false; // The word square is invalid
16                }
17              
18                // Check if the characters at the mirrored positions are not equal
19                if (words.get(rowIndex).charAt(colIndex) != words.get(colIndex).charAt(rowIndex)) {
20                    return false; // The word square is invalid
21                }
22            }
23        }
24        // If all checks pass, the word square is valid
25        return true;
26    }
27}
28

1class Solution {
2public:
3    // Function to check if the given vector of strings forms a valid word square
4    bool validWordSquare(vector<string>& words) {
5        // Get the number of words in the vector
6        int numberOfRows = words.size();
7
8        // Iterate through each word
9        for (int row = 0; row < numberOfRows; ++row) {
10            // Get the length of the current word
11            int wordLength = words[row].size();
12          
13            // Iterate through each character in the current word
14            for (int col = 0; col < wordLength; ++col) {
15                // Check for three conditions:
16                // 1. The column should not be beyond the number of rows
17                // 2. The row should not be beyond the length of the word in the current column
18                // 3. The characters at position [row][col] and [col][row] should match
19                if (col >= numberOfRows ||                                   // Condition 1
20                    row >= words[col].size() ||                              // Condition 2
21                    words[row][col] != words[col][row]) {                    // Condition 3
22                    // If any of the above conditions fail, return false
23                    return false;
24                }
25            }
26        }
27      
28        // If all conditions are satisfied, return true
29        return true;
30    }
31};
32

1// This function checks if the array of words forms a valid word square
2function validWordSquare(words: string[]): boolean {
3    const squareSize = words.length; // squareSize represents the number of words
4
5    // Iterate over each word in the array
6    for (let rowIndex = 0; rowIndex < squareSize; ++rowIndex) {
7        const wordLength = words[rowIndex].length; // Length of the current word
8
9        // Iterate over each character in the word
10        for (let columnIndex = 0; columnIndex < wordLength; ++columnIndex) {
11            // Check if the columnIndex exceeds the number of words (squareSize),
12            // or rowIndex exceeds the length of the word at columnIndex, 
13            // or if the character doesn't match the transposed character
14            if (columnIndex >= squareSize || 
15                rowIndex >= words[columnIndex].length || 
16                words[rowIndex][columnIndex] !== words[columnIndex][rowIndex]) {
17                return false; // The word square is not valid
18            }
19        }
20    }
21
22    return true; // All checks passed, the word square is valid
23}
24

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n * m^2), where n is the number of words in the input list and m is the maximum length of a word in the list. This is because the code uses a nested for-loop that iterates over every character in every word (n * m), and for each character, it potentially checks whether a character exists in the corresponding position in another word (up to m comparisons). However, in reality, the number of operations reduces as the loop checks for out-of-boundary conditions that may break the loop sooner; but in the worst-case scenario, we consider the maximum possible operations.

Space Complexity

The space complexity of the code is O(1). This is because there are no data structures that grow proportionally with the input size. The algorithm only uses a fixed amount of space for variables in the loops regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems