16 lines Python Naive DFS


  • 1
    class Solution(object):
        def numberOfPatterns(self, m, n):
            visited = {}
            ret = [0]
            self.dfsHelper(ret, visited, 0, m, n, -9)
            return ret[0]
            
        def dfsHelper(self, ret, visited, res, m, n, prev):
            if m <= res <= n:
                ret[0] += 1
            if res == n:
                return
            for i in xrange(1, 10):
                if i not in visited:
                    x, y, xp, yp = (i - 1) / 3, (i - 1) % 3, (prev - 1) / 3, (prev - 1) % 3
                    if (5 not in visited and abs(xp - x) == 2 and abs(yp - y) == 2) or ((yp == y and abs(xp - x) == 2) or (xp == x and abs(yp - y) == 2)) and (prev + i) / 2 not in visited:
                        continue
                    visited[i] = 1
                    self.dfsHelper(ret, visited, res + 1, m, n, i)
                    del visited[i]

  • 0
    W

    @jedihy

    Not naive. Instead I think it's straightforward.

    Can you think of an iterative solution?


  • 1

    No, I can't unless I translate the recursive code to iterative one by using stack which makes no sense.


  • -1
    W

    @jedihy

    Yes it makes sense.
    Actually, if you were to translate it into iterative solution, you would probably get MLE...
    Which is why I think the memory limit is too restricted for python non-recursive solutions.


Log in to reply
 

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