# Python DFS, and complexity analysis

• 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 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
``````

• 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)

"""
: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``````

• can you explain your solution

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