422. Valid Word Square
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.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
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 columnj, 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.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Example 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 = 0for the first row.- Examine "AREA" for each character
jfrom 0 to 3 (since "AREA" has 4 letters). - For
j = 0, check ifwords[0][0]('A') equalswords[0][0]('A'). They match. Continue. - For
j = 1, check ifwords[0][1]('R') equalswords[1][0]('B'). They do not match. This means it cannot form a valid word square. ReturnFalse.
- Examine "AREA" for each character
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') equalswords[0][0]('B').words[0][1]('A') equalswords[1][0]('A').words[0][2]('L') equalswords[2][0]('L').words[0][3]('L') equalswords[3][0]('L').
-
Move to the second word "AREA" (
i = 1).words[1][0]('A') equalswords[0][1]('A').words[1][1]('R') equalswords[1][1]('R').words[1][2]('E') equalswords[2][1]('E').words[1][3]('A') equalswords[3][1]('A').
-
Continue with "LEAD" (
i = 2).words[2][0]('L') equalswords[0][2]('L').words[2][1]('E') equalswords[1][2]('E').words[2][2]('A') equalswords[2][2]('A').words[2][3]('D') equalswords[3][2]('D').
-
Finally, check "LADY" (
i = 3).words[3][0]('L') equalswords[0][3]('L').words[3][1]('A') equalswords[1][3]('A').words[3][2]('D') equalswords[2][3]('D').words[3][3]('Y') equalswords[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
221class 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}
281class 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};
321// 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}
24What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
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.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.