# [Python/Java] O(mn/2) time, O(1) space

• Only traverse half of the matrix. Compare the lower-left part with the upper-right. Ignore the diagonal characters.

``````class Solution(object):
def validWordSquare(self, words):
"""
:type words: List[str]
:rtype: bool
"""
rows = len(words)
for i, word in enumerate(words):
cols = len(word)
if cols > rows:
return False
for j in xrange(i + 1, rows):
a = word[j] if j < cols else ''
b = words[j][i] if i < len(words[j]) else ''
if a != b:
return False
return True
``````
``````public class Solution {
public boolean validWordSquare(List<String> words) {
int rows = words.size();
for (int i = 0; i < rows; i++) {
String word = words.get(i);
int cols = word.length();
if (cols > rows) return false;
for (int j = i + 1; j < rows; j++) {
char a = j < cols ? word.charAt(j) : ' ';
char b = i < words.get(j).length() ? words.get(j).charAt(i) : ' ';
if (a != b) return false;
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.