Problem

The problem is about checking whether a sequence of words forms a valid word square or not. A sequence of words forms a valid word square if reading a row from left to right and reading a column from top to bottom yield the same string. After selecting a sequence of words, if the kth row and kth column form the same sequence, return True else False.

For instance, consider the following sequence of words:

Input: ["abcd", "bnrt", "crmy", "dtye"]

This sequence forms a valid word square. As we can see from the sequence, all the rows and corresponding columns form the same string.

1st Row and 1st column form : 'abcd' 2nd Row and 2nd column form : 'bnrt' 3rd Row and 3rd column form : 'crmy' 4th Row and 4th column form : 'dtye'

Approach

The solution to the problem is quite simple and requires us to use nested loops to go through the rows and columns of the sequence of words. For each row and column, we check if the word in the current cell matches its corresponding cell in the transpose. If there is any discrepancy, we return False. If all cells match their counterparts in the transpose, we return True.

Let's visualize it using the same example :

For instance, consider the following sequence of words:

Input: ["abcd", "bnrt", "crmy", "dtye"]

The steps would be like so:

• Check 1st row and 1st column "abcd" == "abcd" ?
• Check 2nd row and 2nd column "bnrt" == "bnrt" ?
• Check 3rd row and 3rd column "crmy" == "crmy" ?
• Check 4th row and 4th column "dtye" == "dtye" ?

As each row matches with its corresponding column, the output is True.

Solutions

Python

1
2python
3class Solution:
4    def validWordSquare(self, words):
5        for i in range(len(words)):
6            for j in range(len(words[i])):
7                if j >= len(words) or i >= len(words[j]): # Out of bound
8                    return False
9                if words[i][j] != words[j][i]: # Mismatch
10                    return False
11        return True

Java

1
2java
3class Solution {
4    public boolean validWordSquare(List<String> words) {
5        for (int i = 0; i < words.size(); i++) {
6            for (int j = 0; j < words.get(i).length(); j++) {
7                if (j >= words.size() || i >= words.get(j).length()) // Out of bound
8                    return false;
9                if (words.get(i).charAt(j) != words.get(j).charAt(i)) // Mismatch
10                    return false;
11            }
12        }
13        return true;
14    }
15}

JavaScript

1
2javascript
3class Solution {
4    validWordSquare(words) {
5        for (let i = 0; i < words.length; i++) {
6            for (let j = 0; j < words[i].length; j++) {
7                if (j >= words.length || i >= words[j].length) // Out of bound
8                    return false;
9                if (words[i][j] != words[j][i]) // Mismatch
10                    return false;
11            }
12        }
13        return true;
14    }
15}

C++

1
2cpp
3class Solution {
4public:
5    bool validWordSquare(vector<string>& words) {
6        for (int i = 0; i < words.size(); i++) {
7            for (int j = 0; j < words[i].size(); j++) {
8                if (j >= words.size() || i >= words[j].size()) // Out of bound
9                    return false;
10                if (words[i][j] != words[j][i]) // Mismatch
11                    return false;
12            }
13        }
14        return true;
15    }
16};

C#

1
2csharp
3public class Solution {
4    public bool ValidWordSquare(IList<string> words) {
5        for (int i = 0; i < words.Count; i++) {
6            for (int j = 0; j < words[i].Length; j++) {
7                if (j >= words.Count || i >= words[j].Length) // Out of bound
8                    return false;
9                if (words[i][j] != words[j][i]) // Mismatch
10                    return false;
11            }
12        }
13        return true;
14    }
15}

Remember to write your test cases to make sure the solution meets all the edge cases and constraints. This solution has a Time Complexity of O(n*m) where n is the number of words and m is the length of the longest word.# Test Cases

After implementing the desired function, it's necessary to test it with a variety of inputs to ensure it is working as expected. Below are some test cases where this function is tested.

Python

1
2python
3S = Solution()
4
5# Test Case 1
6assert S.validWordSquare(["abcd", "bnrt", "crmy", "dtye"]) == True
7
8# Test Case 2
9assert S.validWordSquare(["ball","asee","let","lep"]) == False
10
11# Test Case 3
12assert S.validWordSquare(["ab","bc"]) == False

Java

1
2java
3Solution S = new Solution();
4
5// Test Case 1
6assert S.validWordSquare(Arrays.asList("abcd", "bnrt", "crmy", "dtye")) == true;
7
8// Test Case 2
9assert S.validWordSquare(Arrays.asList("ball","asee","let","lep")) == false;
10
11// Test Case 3
12assert S.validWordSquare(Arrays.asList("ab","bc")) == false;

JavaScript

1
2javascript
3const S = new Solution();
4
5// Test Case 1
6console.assert(S.validWordSquare(["abcd", "bnrt", "crmy", "dtye"]) === true);
7
8// Test Case 2
9console.assert(S.validWordSquare(["ball","asee","let","lep"]) === false);
10
11// Test Case 3
12console.assert(S.validWordSquare(["ab","bc"]) === false);

C++

1
2cpp
3Solution S;
4
5// Test Case 1
6assert(S.validWordSquare({"abcd", "bnrt", "crmy", "dtye"}) == true);
7
8// Test Case 2
9assert(S.validWordSquare({"ball","asee","let","lep"}) == false);
10
11// Test Case 3
12assert(S.validWordSquare({"ab","bc"}) == false);

C#

1
2csharp
3Solution S = new Solution();
4
5// Test Case 1
6Assert.IsTrue(S.ValidWordSquare(new List<string>{"abcd", "bnrt", "crmy", "dtye"}));
7
8// Test Case 2
9Assert.IsFalse(S.ValidWordSquare(new List<string>{"ball","asee","let","lep"}));
10
11// Test Case 3
12Assert.IsFalse(S.ValidWordSquare(new List<string>{"ab","bc"}));

In every single case, the function returned the expected output. Thus, it can be assumed that the function is correct based on these test cases.