Different outputs from local machine and the OJ


  • 0
    D

    def calDistance(me,other):

    if(me==other):
        return 0
    
    lens=len(me)
    count=0
    for i in xrange(lens):
        if(me[i]!=other[i]):
            count+=1
    
    return count
    

    class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dict):

        #here I need to build one simple structure 
        distance={}
        visited={}
        if(dict==None):
            return 0
        
        startCount=0
        endCount=0
        wordCount=0
        startOne=[]
        endOne=[]
        
        endDistanceMap={}
        startDistanceMap={}
        
        wordSize=len(start)
        
        for i in xrange(wordSize+1):
            endDistanceMap[i]=[]
            startDistanceMap[i]=[]
        
        for word in dict:
            startDistance=calDistance(word,start)
            endDistance=calDistance(word,end)
            startCount+=(startDistance==1)
            endCount+=(endDistance==1)
            wordCount+=1
            endDistanceMap[endDistance].append(word)
            startDistanceMap[startDistance].append(word)
            
        
        
    
        #print "startCount:{}".format(startCount)
        #print "endCount:{}".format(endCount)
        
        #print "wordCount:{}".format(wordCount)
        #print "startDistanceMap[1]:{}".format(startDistanceMap[1])
        if(startCount==0 or endCount==0):
            return 0
        
        
            
        if(end in startDistanceMap[1]):
            return 2
        
        newOnes=startDistanceMap[1]
        referMap=startDistanceMap
        targetEnd=end
        
        if(endCount<startCount):
            targetEnd=start
            referMap=endDistanceMap
            newOnes=endDistanceMap[1]
            
        #newOnes=startDistanceMap[1]
        #addOnes=[]
        i=1
        
        while(newOnes!=[]):
            
            posNext=[]
            addOnes=[]
            if(referMap.has_key(i+1)):
                posNext=referMap[i+1]
            
            if(posNext==[]):
                return 0
            
            
            for pNext in posNext:
                distanceMin=wordSize
                
                
                for pre in newOnes:
                    
                    wordDistance=calDistance(pre,pNext)
                    
                    if(wordDistance<distanceMin):
                        distanceMin=wordDistance
                
                if(distanceMin==1):
                    #mean this one is reachable
                    if(pNext==targetEnd):
                        #print "pNext==targetend"
                        return i+2
                    
                    endDistance=calDistance(pNext,targetEnd)
                    if(endDistance==1):
                        #print "next case"
                        return i+3
                    addOnes.append(pNext)
                else:
                    
                    if(referMap.has_key(i+i+1)):
                        #this is very important idea 
                        referMap[i+i+1].append(pNext)
                    else:
                        referMap[i+i+1]=[pNext]
            
            newOnes=addOnes
            #print "addOnes:{}".format(len(addOnes))
           
            i+=1
            
        
        
        return 0

  • 0
    D

    I try on other machine. OJ produce the different one.


Log in to reply
 

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