Halp Python


  • 0

    Thought this would be a perfectly valid solution but I seem to be missing a few patterns?? I've accounted for the 1-> 8 case in this solution but I'm having a hard time trying to figure out why this is failing for m=1, n=3

    Output:
    369
    Expected:
    385

    :( Please halp/explain

    def DFS(i, j, m, n, patterns, screen):
        stack = []
        stack.append((i, j, set())) # i, j, visited
        while stack:
            i, j, visited = stack.pop()
            visited = visited.union([screen[i][j]])  # creates new set instead of modifying reference
            if len(visited)> n:
                continue
            if m <= len(visited)<= n:
                patterns[0] += 1
            # check all 16 degrees of freedom
            for n_x, n_y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1], [i+1, j+1],[i+1, j-1],[i-1, j+1],[i-1, j-1], 
                             [i+2, j+1], [i-2, j+1], [i+2, j-1], [i-2, j-1], [i+1, j+2], [i-1, j+2], [i+1, j-2], [i-1, j-2]]:
                if n_x < 0 or n_x >= len(screen) or n_y < 0 or n_y >= len(screen[0]):
                    continue
                elif screen[n_x][n_y] in visited:  # check already visited
                    continue
                else:
                    stack.append((n_x, n_y, visited))
    
    class Solution(object):
        def numberOfPatterns(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            patterns = [0]  # list for referencing
            screen = [[1,2,3],
                      [4,5,6],
                      [7,8,9]]
            for i in xrange(len(screen)):
                for j in xrange(len(screen[0])):
                    DFS(i, j, m, n, patterns, screen)
            return patterns[0]
    

Log in to reply
 

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