Solution Explanation for Valid Word Square

The problem asks whether a given list of strings forms a valid word square. A word square is defined as a set of strings where the i-th row and i-th column read the same string for all valid indices i.

Approach: Iterative Check

The most efficient approach is a direct iterative check. We iterate through the input list words. For each string (row) in words, we iterate through its characters. During this inner iteration, we perform two crucial checks:

1. Bounds Check: We verify that both the row index (i) and column index (j) are within the valid bounds of the words array and that the respective strings in words are long enough. If either index is out of bounds, it means we've encountered an incomplete square, and we can immediately return false.

2. Character Match: We compare the character at words[i][j] with the character at words[j][i]. If these characters don't match, it violates the word square condition, and we return false.

If both the bounds check and character match pass for all characters in all rows, it means we have a valid word square, and we return true.

Time and Space Complexity Analysis

• Time Complexity: The solution iterates through each string in words (outer loop) and then iterates through the characters of each string (inner loop). The number of iterations is proportional to the sum of lengths of all strings in words. In the worst case, where all strings have equal length n, the time complexity would be O(n^2).

• Space Complexity: The solution uses a constant amount of extra space for variables like loop counters. Therefore, the space complexity is O(1).

Code Implementation in Multiple Languages

The following code snippets demonstrate the iterative checking approach in several programming languages:

Python:

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        m = len(words)
        for i, w in enumerate(words):
            for j, c in enumerate(w):
                if j >= m or i >= len(words[j]) or c != words[j][i]:
                    return False
        return True
 

Java:

class Solution {
    public boolean validWordSquare(List<String> words) {
        int m = words.size();
        for (int i = 0; i < m; ++i) {
            int n = words.get(i).length();
            for (int j = 0; j < n; ++j) {
                if (j >= m || i >= words.get(j).length()) {
                    return false;
                }
                if (words.get(i).charAt(j) != words.get(j).charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}

C++:

class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        int m = words.size();
        for (int i = 0; i < m; ++i) {
            int n = words[i].size();
            for (int j = 0; j < n; ++j) {
                if (j >= m || i >= words[j].size() || words[i][j] != words[j][i]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Go:

func validWordSquare(words []string) bool {
	m := len(words)
	for i, w := range words {
		for j := range w {
			if j >= m || i >= len(words[j]) || w[j] != words[j][i] {
				return false
			}
		}
	}
	return true
}

TypeScript:

function validWordSquare(words: string[]): boolean {
    const m = words.length;
    for (let i = 0; i < m; ++i) {
        const n = words[i].length;
        for (let j = 0; j < n; ++j) {
            if (j >= m || i >= words[j].length || words[i][j] !== words[j][i]) {
                return false;
            }
        }
    }
    return true;
}

These code examples all implement the same efficient algorithm, differing only in syntax and specific language features. They all achieve a time complexity of O(n^2) and a space complexity of O(1).