Python DFS, and complexity analysis


  • 10

    Similar to other solutions out there.

    The code has O(1) time complexity, because all the possible watch combinations (valid or invalid) can't be more that 12 * 59.
    Regarding space complexity, it's also O(1) cause the DFS will have depth of maximum n, which can't be more than 9 as per problem boundary.

    class Solution(object):
        def readBinaryWatch(self, n):
            
            def dfs(n, hours, mins, idx):
                if hours >= 12 or mins > 59: return
                if not n:
                    res.append(str(hours) + ":" + "0" * (mins < 10) + str(mins))
                    return
                for i in range(idx, 10):
                    if i < 4: 
                        dfs(n - 1, hours | (1 << i), mins, i + 1)
                    else:
                        k = i - 4
                        dfs(n - 1, hours, mins | (1 << k), i + 1)
            
            res = []
            dfs(n, 0, 0, 0)
            return res
    

  • 0
    I

    Nice soln! I did something similar but without any bit manipulation. Do you think the interviewer would care if we don't use bit manip as long as we get the answer? this is mine for ref:

    class Solution(object):
        def calc_times(self, leds, idx, curr_hr, curr_min, result, n):
            if n == 0:
                if curr_min < 10:
                    result.append(str(curr_hr) + ":0" + str(curr_min))
                else:
                    result.append(str(curr_hr) + ":" + str(curr_min))
                
            elif n > 0 and idx < len(leds):
                if 0 <= idx <= 3 and curr_hr + leds[idx] < 12:
                    self.calc_times(leds, idx+1, curr_hr + leds[idx], curr_min, result, n-1)
                elif idx > 3 and curr_min + leds[idx] < 60:
                    self.calc_times(leds, idx+1, curr_hr, curr_min + leds[idx], result, n-1)
                self.calc_times(leds, idx+1, curr_hr, curr_min, result, n)
        
        def readBinaryWatch(self, num):
            """
            :type num: int
            :rtype: List[str]
            """
            result = []
            leds = [8,4,2,1,32,16,8,4,2,1]
            self.calc_times(leds, 0, 0, 0, result, num)
            return result

Log in to reply
 

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