Python 500ms - 3 lines BFS with explanation - intersection of sets


  • 0
    A

    For each 'level' I have two sets, one for the targets and one for the roots to use
    At the beginning the targets set is simply the initial input

    In the while loop, I check the intersection of these sets:

    • if it exists, it means that one solution exists at such level, therefore I exit the loop
    • if it does not exist, I recreate the set of targets with all the positive differences between the current element in set of targets and the roots

    hope you won't criticize the way I declared the variables in order to use few lines :)

    def numSquares(target):
        
        level, targets, roots = 0, set({target}), set([(x+1)**2 for x in xrange(int(target**0.5))])
    
        while targets: targets, level =  None if targets.intersection(roots) else set([x-y for x in targets for y in roots if x-y > 0]), level + 1
        
        return level
    
    

Log in to reply
 

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