combination recursive 50ms solution Python


  • 0
    V

    This was the most intuitive approach to me, but it's not such a short solution. I'm using Pauli's inclusion/exclusion principle.

    class Solution(object):
        def readBinaryWatch(self, num):
            """
            :type num: int
            :rtype: List[str]
            """
            if num == 0:
                return ["0:00"]
            arr = [('h', 1), ('h', 2), ('h', 4), ('h', 8), ('m', 1), ('m', 2), ('m', 4), ('m', 8), ('m', 16), ('m', 32)]
            return self.comboUtil(arr, num, [None]*num, 0, 0)
        
        def comboUtil(self, arr, num, data, datai, arri):
            if datai == num:
                return self.computeTime(data)
            
            if arri >= len(arr):
                return []
            
            ret = []
            curData = data[:]
            # inclusion
            curData[datai] = arr[arri]
            ret += self.comboUtil(arr, num, curData, datai + 1, arri + 1)
            # exclusion
            ret += self.comboUtil(arr, num, curData, datai, arri + 1)
            return ret
        
        def computeTime(self, data):
            hrs = 0
            mins = 0
            for e in data:
                if e[0] == 'm':
                    mins += e[1]
                else:
                    hrs += e[1]
            
            if mins > 59:
                return []
            
            if hrs > 11:
                return []
    
            if mins < 10:
                mins = "0" + str(mins)
                
            return ["{0}:{1}".format(hrs, mins)]
            
    

Log in to reply
 

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