# Readable Python without tricks, optimal O(n) time O(1) space

• ``````class Solution(object):
def validWordSquare(self, words):
if len(words) != len(words[0]):
return False
for row in xrange(len(words)):
for col in xrange(len(words[row])):
try:
if words[row][col] != words[col][row]:
return False
except:
return False
return True
``````

• ``````            if row == col:
continue
``````

Why are you doing that? Isn't that unnecessary extra code and making your solution slower?

• @ManuelP If `row == col`, you'll just compare the same value to itself in the try/catch.

With or without it, it's O(n). I think whether it's faster will depend on how the Python interpreter implements the try/catch, which is the overhead we avoid by continuing on `row == col`.

Having said that, situations where `row == col` become less and less frequent as the size of `n` grows. I suspect for smaller values of `n`, the continue improves performance slightly, but for very large values of `n`, it slows it down slightly. But in either case, the effect is minor and the algorithm is O(n).

Edit: Forgot to mention the most important thing, which is that `row == col` makes the code slightly less understandable for no real benefit. So I agree it shouldn't be there. :)

• Yeah, it doesn't make a big difference, but except for very small inputs, it does make things slower. Which I'd say is bad if it was an attempt to make things faster. And it looked like it was such an attempt.

I did a little test with m×m fields filled with just "a" characters. The problem allows up to m=500, I went a little higher as well. The results:

``````   m  Sol1  Sol2  Sol3
4 13.26 13.78 12.78
8  9.71  9.74  8.75
16  8.52  8.07  7.13
32  8.13  7.46  6.48
64  7.75  7.21  6.34
128  7.82  7.06  6.25
256  7.76  7.03  6.14
512  7.88  7.25  6.25
1024  8.22  7.36  6.55
2048  9.58  8.88  8.16
4096 11.87 11.27 10.48
``````

"Sol1" are the times of your original, "Sol2" are the times of your updated version, and "Sol3" is from another version where I pulled the try/catch out of the loops. The times for different m are roughly the same because for larger m, I do fewer runs.

The complete code:

``````class Solution1(object):
def validWordSquare(self, words):
if len(words) != len(words[0]):
return False
for row in xrange(len(words)):
for col in xrange(len(words[row])):
if row == col:
continue
try:
if words[row][col] != words[col][row]:
return False
except:
return False
return True

class Solution2(object):
def validWordSquare(self, words):
if len(words) != len(words[0]):
return False
for row in xrange(len(words)):
for col in xrange(len(words[row])):
try:
if words[row][col] != words[col][row]:
return False
except:
return False
return True

class Solution3(object):
def validWordSquare(self, words):
if len(words) != len(words[0]):
return False
try:
for row in xrange(len(words)):
for col in xrange(len(words[row])):
if words[row][col] != words[col][row]:
return False
except:
return False
return True

from timeit import timeit
for e in range(2, 13):
m = 2**e
print '%4d' % m,
n = m**2
words = ['a' * m for _ in range(m)]
for Solution in Solution1, Solution2, Solution3:
f = Solution().validWordSquare
print '%5.2f' % timeit(lambda: f(words), number=2**24/n),
print
``````

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