LeetCode 0681. Next Closest Time Solution in Java & Python | Explanation + Code

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: time = "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: time = "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.

 

Constraints:

• time.length == 5
• time is a valid time in the form "HH:MM".
• 0 <= HH < 24
• 0 <= MM < 60

Solutions

Solution 1

PythonJava

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(code-box)

class Solution { private int t; private int d; private String ans; private Set<Character> s; public String nextClosestTime(String time) { t = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3)); d = Integer.MAX_VALUE; s = new HashSet<>(); char mi = 'z'; for (char c : time.toCharArray()) { if (c != ':') { s.add(c); if (c < mi) { mi = c; } } } ans = null; dfs(""); if (ans == null) { ans = "" + mi + mi + ":" + mi + mi; } return ans; } private void dfs(String curr) { if (curr.length() == 4) { if (!check(curr)) { return; } int p = Integer.parseInt(curr.substring(0, 2)) * 60 + Integer.parseInt(curr.substring(2)); if (p > t && p - t < d) { d = p - t; ans = curr.substring(0, 2) + ":" + curr.substring(2); } return; } for (char c : s) { dfs(curr + c); } } private boolean check(String t) { int h = Integer.parseInt(t.substring(0, 2)); int m = Integer.parseInt(t.substring(2)); return 0 <= h && h < 24 && 0 <= m && m < 60; } }(code-box)