
Problem Statement
Given an array of strings named 'words', we need to determine if these strings can form a valid word square. A valid word square is defined as a sequence where the string at position 'k' reads the same horizontally (rows) and vertically (columns). This must hold true for all possible values of 'k' within the bounds of the square, where the bounds are determined by the size of the largest row or column. Each input comprises only lowercase English letters.
Examples
Example 1
Input:
words = ["abcd","bnrt","crmy","dtye"]
Output:
true
Explanation:
The 1st row and 1st column both read "abcd". The 2nd row and 2nd column both read "bnrt". The 3rd row and 3rd column both read "crmy". The 4th row and 4th column both read "dtye". Therefore, it is a valid word square.
Example 2
Input:
words = ["abcd","bnrt","crm","dt"]
Output:
true
Explanation:
The 1st row and 1st column both read "abcd". The 2nd row and 2nd column both read "bnrt". The 3rd row and 3rd column both read "crm". The 4th row and 4th column both read "dt". Therefore, it is a valid word square.
Example 3
Input:
words = ["ball","area","read","lady"]
Output:
false
Explanation:
The 3rd row reads "read" while the 3rd column reads "lead". Therefore, it is NOT a valid word square.
Constraints
1 <= words.length <= 500
1 <= words[i].length <= 500
words[i]
consists of only lowercase English letters.
Approach and Intuition
To solve this problem correctly and efficiently, we can follow a systematic approach that checks if every column and row in the given square aligns as per the definition of a word square. Here's a step-by-step breakdown of what this approach looks like:
Validation First: Before diving into checking each row and column, ensure that the length of the list of words matches the length of the longest word among them. This helps guarantee that the grid can potentially form a valid square.
Iterate Through Strings: For each string in the list, ensure that the character at any position 'i' matches the 'i-th' character of each subsequent string. This is crucial since it directly corresponds to checking the kth row against the kth column for every k.
Check Earlier Terminations: If any mismatches occur during the validation of each row and column correspondence (in character alignment), the function can immediately return
false
, reducing unnecessary computations.Edge Cases: Consider the lengths and number of strings carefully:
All Strings of Equal Length: This is the best-case scenario where each string is as long as the list itself.
Varying String Lengths: Even if strings are of varying lengths but by design (from input) align properly due to interspersing shorter strings, verify all intersections regardless.
Return the Output: If after all checks, no discrepancies are found, return
true
.
Applying these steps correctly based on the given constraints will help in validating or refuting whether the given strings can form a word square. Use the example snippets provided to visualize corner cases and typical scenarios which further ground the understanding of the problem and its solution.
Solutions
- C++
class Solution {
public:
bool isValidWordSquare(vector<string>& words) {
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].length(); j++) {
if (j >= words.size() ||
i >= words[j].length() ||
words[i][j] != words[j][i]) {
return false;
}
}
}
return true;
}
};
This solution checks whether a given list of words forms a valid word square in C++. A word square is a matrix of words that read the same horizontally and vertically. The implementation follows these steps:
- Iterate over each word in the list.
- For each character in a word, verify if the corresponding position vertically across the words holds the matching character.
- If a mismatch occurs or the indices go out of the valid range, return false, indicating the words do not form a valid word square.
- If all conditions are satisfied, return true.
The primary checks involve ensuring that for each character words[i][j]
, the corresponding vertical character words[j][i]
exists and is identical. If either the row or column extends beyond the size of the words list or the characters do not match, the function immediately returns false. Otherwise, after checking all the words and characters without finding any issues, the function returns true, confirming the list of words forms a valid word square.
- Java
class Solution {
public boolean isWordSquare(List<String> wordsList) {
for (int rowIndex = 0; rowIndex < wordsList.size(); ++rowIndex) {
for (int colIndex = 0; colIndex < wordsList.get(rowIndex).length(); ++colIndex) {
if (colIndex >= wordsList.size() ||
rowIndex >= wordsList.get(colIndex).length() ||
wordsList.get(rowIndex).charAt(colIndex) != wordsList.get(colIndex).charAt(rowIndex)) {
return false;
}
}
}
return true;
}
}
The presented Java solution implements a method to validate whether a list of strings forms a valid word square. A word square is a sequence of words arranged into a square grid, where the words run the same both horizontally and vertically.
- Begin by iterating over each word in the
wordsList
with a nested loop structure. The outer loop’s variablerowIndex
represents the current row of words, and the inner loop’s variablecolIndex
represents the corresponding character in the current word. - Check for three conditions during the character matching:
- Verify if
colIndex
is less than the total number of words. This ensures the column exists for the corresponding row character. - Check if
rowIndex
is less than the length of the word at the current column. This confirms the row character exists in the current column word. - Compare characters: the character at the current row and column (
wordsList.get(rowIndex).charAt(colIndex)
) should match the character at the transposed position (wordsList.get(colIndex).charAt(rowIndex)
).
- Verify if
- If any condition fails, the method immediately returns
false
, indicating the words do not form a valid word square. - If all iterations pass the checks without returning
false
, then after the loops complete, returntrue
as the list represents a valid word square.
This solution efficiently checks for the validity of a word square by ensuring every character position aligns correctly across both rows and columns, leveraging a direct indexing approach that avoids any transformations or additional data structures.
- JavaScript
var isWordSquare = function(wordList) {
for (let index1 = 0; index1 < wordList.length; ++index1) {
for (let index2 = 0; index2 < wordList[index1].length; ++index2) {
if (index2 >= wordList.length ||
index1 >= wordList[index2].length ||
wordList[index1][index2] != wordList[index2][index1]){
return false;
}
}
}
return true;
};
The problem "Valid Word Square" can be solved using the JavaScript function isWordSquare
. This function checks if a given list of words forms a valid word square. A word square is a square grid of words where the kth row and column read the exact same string.
Here's a concise breakdown of the solution:
- The function
isWordSquare
takeswordList
as an argument, which is an array of strings. - Iterate through each word in
wordList
using a double nested loop whereindex1
represents the row index andindex2
represents the column index. - For every character position
(index1, index2)
:- Check if the current column
index2
exceeds the number of words in the list or if the current rowindex1
exceeds the length of the word at the current column. This helps in ensuring that the matrix is symmetric. - Check if the character at the
(index1, index2)
position matches the character at the(index2, index1)
position. - If any of the above checks fail, return
false
indicating that the words do not form a valid word square.
- Check if the current column
- If all comparisons are successfully symmetric, return
true
indicating a valid word square.
This JavaScript solution efficiently determines the validity of a word arrangement as a square by leveraging column and row symmetry checks. The function uses straightforward indexing and comparison to ensure each row matches its corresponding column across the entire matrix.
- Python
class Solution:
def isValidWordSquare(self, words: List[str]) -> bool:
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
This Python3 solution checks whether a given list of strings forms a valid word square. A word square is valid if the words line along the rows and columns consistently, meaning the character at the i-th
row and j-th
column must match the character at the j-th
row and i-th
column. Here’s how the function operates:
- Iterate over each word and character in the
words
list using two nested loops, wherei
represents the current word index andj
represents the character index in the word. - Check if the current column
j
exceeds the number of words or if the current word length at wordj
is less thani
. This step ensures that characters align properly without exceeding their respective string lengths. - Compare the character at the
i-th
row andj-th
column with the character at thej-th
row andi-th
column. If they don’t match, returnFalse
. - If all checks pass through without breaking, return
True
after exiting the loops, confirming the words form a valid word square.
This method uses direct index access and simple conditional checks to efficiently validate the word square without the need for additional data structures, providing a solution with clear and understandable logic.
No comments yet.