Valid Word Square

Updated on 04 July, 2025
Valid Word Square header image

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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++
cpp
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:

  1. Iterate over each word in the list.
  2. For each character in a word, verify if the corresponding position vertically across the words holds the matching character.
  3. 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.
  4. 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
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 variable rowIndex represents the current row of words, and the inner loop’s variable colIndex 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)).
  • 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, return true 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
js
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 takes wordList as an argument, which is an array of strings.
  • Iterate through each word in wordList using a double nested loop where index1 represents the row index and index2 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 row index1 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.
  • 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
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:

  1. Iterate over each word and character in the words list using two nested loops, where i represents the current word index and j represents the character index in the word.
  2. Check if the current column j exceeds the number of words or if the current word length at word j is less than i. This step ensures that characters align properly without exceeding their respective string lengths.
  3. Compare the character at the i-th row and j-th column with the character at the j-th row and i-th column. If they don’t match, return False.
  4. 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.

Comments

No comments yet.