Leetcode: Next Closest Time

Next Closest Time

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/next-closest-time
## Basic Ideas: Only pow(4, 4) combinations
##      Get all of them, and rule out the invalid onces
##      Convert the time string to seconds
##      Compare the absolute diff with rotated enforced
## Assumption: "11:11" -> "11:11"
## Complexity: Time O(1), Space O(1)
class Solution:
    def nextClosestTime(self, time):
        :type time: str
        :rtype: str
        import sys
        ch_set = set(time)
        if len(ch_set) == 1: return time

        l = [""]
        for i in range(4):
            l2 = []
            for ch in ch_set:
                for item in l:
                    if i == 1:
                        l2.append("%s%s:" % (item, ch))
                        l2.append("%s%s" % (item, ch))
            l = l2

        minutes = self.getMinutes(time)
        min_diff, index  = sys.maxsize, None
        total_minutes = 24*60
        for i in range(len(l)):
            t = l[i]
            # check whether t is valid
            if int(t[0])*10+int(t[1]) >= 24: continue
            if int(t[3])*10+int(t[4]) >= 60: continue

            diff = (self.getMinutes(t)-minutes+total_minutes) % total_minutes
            if diff == 0: continue

            if min_diff > diff:
                min_diff, index = diff, i

        return l[index]

    def getMinutes(self, time):
        return (int(time[0])*10 + int(time[1]))*60+(int(time[3])*10 + int(time[4]))

Share It, If You Like It.

Leave a Reply

Your email address will not be published.