Python simple DFS solution with bit manipulation


  • 0
    Y
    class Solution(object):
        def readBinaryWatch(self, num):
            """
            :type num: int
            :rtype: List[str]
            """
            
            light_num = 10
            self.res = []
            def dfs(start, light_left, h, m):
                if light_left == 0:
                    if h <= 11 and m <= 59:
                        self.res.append(str(h) + ":" + "%02d" % m)
                    return
                
                for i in xrange(start, light_num - light_left + 2):
                    if i <= 4:
                        dfs(i+1, light_left - 1, h + (1 << (i-1)), m)
                    else:
                        dfs(i+1, light_left - 1, h, m + (1 << (i-5)) )
            
            dfs(1, num, 0, 0)
            
           return self.res
    

    A single value i is used to indicate which light is on.
    if i <= 4, it is for hours
    if 4 < i <= 10, it is for minutes


Log in to reply
 

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