Saturday, March 2, 2019

Leetcode 681. Next Closest Time

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.

Code (Java):

class Solution {
    public String nextClosestTime(String time) {
        int original = getElapsedMinutes(time);
        int minDiff = Integer.MAX_VALUE;
        int ans = original;

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < time.length(); i++) {
            if (time.charAt(i) != ':') {
                set.add(Character.getNumericValue(time.charAt(i)));
            }
        }

        for (int h1 : set) {
            for (int h2 : set) {
                if (h1 * 10 + h2 < 24) {
                    for (int m1 : set) {
                        for (int m2 : set) {
                            if (m1 * 10 + m2 < 60) {
                                int currTime = (h1 * 10 + h2) * 60 + (m1 * 10 + m2);
                                int diff = Math.floorMod(currTime - original, 24 * 60);
                                if (diff > 0 && diff < minDiff) {
                                    ans = currTime;
                                    minDiff = diff; 
                                }
                            }
                        }
                    }
                }
            }
        }

        return String.format("%02d:%02d", ans / 60, ans % 60);
    }
    
    private int getElapsedMinutes(String time) {
        int hour = Character.getNumericValue(time.charAt(0)) * 10 + Character.getNumericValue(time.charAt(1));
        int min = Character.getNumericValue(time.charAt(3)) * 10 + Character.getNumericValue(time.charAt(4));
        
        return hour * 60 + min;
    }
}

Discussion:
One corner case to consider is if the time is 11:11, the next time should be 11:11 as it's for next day. But int the code since we check diff > 0, the ans will return 0. To handle this case, the initial value should be original time.

No comments:

Post a Comment