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


  • 0
    F
    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
    

  • 0
    M

    @FlorenceMachine said in Readable Python without tricks, optimal O(n) time O(1) space:

                if row == col: 
                    continue
    

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


  • 0
    F

    @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. :)


  • 1
    M

    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
    

Log in to reply
 

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