Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/681.html
681. Next Closest Time
Level
Medium
Description
Given a time represented in the format “HH:MM”, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.
You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.
Example 1:
Input: “19:34”
Output: “19:39”
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.
Example 2:
Input: “23:59”
Output: “22:22”
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day’s time since it is smaller than the input time numerically.
Solution
Simulate all possible times minute by minute. If a time can be formed by reusing the current digit, return the time.
When returning the time, use String.format
to convert it into the required format “HH:MM”.
-
class Solution { public String nextClosestTime(String time) { String hourStr = time.substring(0, 2), minuteStr = time.substring(3); Set<Integer> set = new HashSet<Integer>(); for (int i = 0; i < 2; i++) { set.add(hourStr.charAt(i) - '0'); set.add(minuteStr.charAt(i) - '0'); } int[] timeArray = {Integer.parseInt(hourStr), Integer.parseInt(minuteStr)}; for (int i = 1; i <= 1440; i++) { next(timeArray); if (isReuse(timeArray, set)) { String nextTime = String.format("%02d:%02d", timeArray[0], timeArray[1]); return nextTime; } } return time; } public void next(int[] timeArray) { timeArray[1]++; if (timeArray[1] >= 60) { timeArray[1] %= 60; timeArray[0]++; } if (timeArray[0] >= 24) timeArray[0] %= 24; } public boolean isReuse(int[] timeArray, Set<Integer> set) { int hour = timeArray[0], minute = timeArray[1]; if (!set.contains(hour / 10)) return false; else if (!set.contains(hour % 10)) return false; else if (!set.contains(minute / 10)) return false; else if (!set.contains(minute % 10)) return false; else return true; } }
-
class Solution: def nextClosestTime(self, time: str) -> str: def check(t): h, m = int(t[:2]), int(t[2:]) return 0 <= h < 24 and 0 <= m < 60 def dfs(curr): if len(curr) == 4: if not check(curr): return nonlocal ans, d p = int(curr[:2]) * 60 + int(curr[2:]) if t < p < t + d: d = p - t ans = curr[:2] + ':' + curr[2:] return for c in s: dfs(curr + c) s = {c for c in time if c != ':'} t = int(time[:2]) * 60 + int(time[3:]) d = inf ans = None dfs('') if ans is None: mi = min(int(c) for c in s) ans = f'{mi}{mi}:{mi}{mi}' return ans