Question

681. Next Closest Time

中文文档

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

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

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;
  }
}