Super Straightforward Python Solution - Finite State Machine


  • 0
    M
    class Solution(object):
        def spiralOrder(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[int]
            """
            if matrix==None or len(matrix)==0 or len(matrix[0])==0:
                return matrix
            
            ret=[]
            
            m=len(matrix)
            n=len(matrix[0])
            
            visitedr=[0]*(n+2)
            visited=[]
            for i in range(m+2):
                visited.append(visitedr[:])
            
            visited[0]=visited[-1]=[1]*(n+2)
            for i in range(m+2):
                visited[i][0]=visited[i][-1]=1
                
            #print visited
            dirc=0
            i,j=0,0
            
            while visited[i+1][j+1]==0:
                visited[i+1][j+1]=1
                ret.append(matrix[i][j])
                if dirc==0:
                    if visited[i+1][j+2]!=1:
                        j+=1
                    else:
                        dirc=1
                        i+=1
                elif dirc==1:
                    if visited[i+2][j+1]!=1:
                        i+=1
                    else:
                        dirc=2
                        j-=1
                elif dirc==2:
                    if visited[i+1][j]!=1:
                        j-=1
                    else:
                        dirc=3
                        i-=1
                elif dirc==3:
                    if visited[i][j+1]!=1:
                        i-=1
                    else:
                        dirc=0
                        j+=1
                        
            return ret
    

    Store all the visited cells and once we hit a visited cell, we turn down/left/up/right according to the previous state (we jump between 4 states according to previous state).


Log in to reply
 

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