Store each level using hash table DFS [Accepted]


  • 0
    L
    • Traverse whole nestedLists (DFS), store all integers into a dictionary base on their weights.
    • Using 0 to -n (0<n) to represent weights(levels).
    • Using formula (level + maxLevel) * sum(Integer List for level m]), maxLevel is (absolute value of the lastest level) + 1
    class Solution(object):
        def depthSumInverse(self, nestedList):
            global maxLevel
            maxLevel = 0
            dic = {}
            
            def helper(nestedList, level):
                global maxLevel
                for l in nestedList:
                    # record the lastest level
                    maxLevel = min(level, maxLevel)                 
                    if l.isInteger():
                        if level in dic:
                            dic[level].append(l.getInteger())
                        else:
                            dic[level] = [l.getInteger()]
                    else:
                        # read nestedList from next level
                        helper(l.getList(), level-1)                
    
            helper(nestedList, 0)  
            weightedSUM = 0
            
            # each level in dic should be updated by adding this
            maxLevel = abs(maxLevel) + 1                            
            for level in dic:
                # calculate the weighted sum for all levels
                weightedSUM += (level + maxLevel) * sum(dic[level])     
            
            return weightedSUM
    

Log in to reply
 

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