Leetcode: 2437. Number of Valid Clock Times

Problem Statement

Understand the problem

Count the number of valid time string by filling out the position with ?.

Devise a plan

In this problem, the Pattern: Small constraints could allow a brute-force solution. For each unknown position, we try to fill with numbers from 0 to 9. On the end, we count 1 if the time is valid or 0 otherwise. Time complexity is \(O(9^4)=O(1)\) and space is \(O(1)\).

Carry out the plan

class Solution:
    def countTime(self, time: str) -> int:
        if "?" not in time:
            return int(0 <= int(time[:2]) <= 23 and 0 <= int(time[3:]) <= 59)
        i = time.find("?")
        ans = 0
        for d in range(ord("0"), ord("9") + 1):
            ans += self.countTime(time[:i] + chr(d) + time[i + 1 :])
        return ans