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.

答案

class Solution {
    int diff = Integer.MAX_VALUE;
    int h = 0, m = 0;
    public String nextClosestTime(String time) {
        // Extract hour and minutes from time
        int[] select = new int[4];
        String[] parts = time.split(":");
        int hour = Integer.parseInt(parts[0]);
        int min = Integer.parseInt(parts[1]);
        
        Set<Integer> digits = new HashSet<>();
        digits.add(Integer.parseInt(Character.toString(time.charAt(0))));
        digits.add(Integer.parseInt(Character.toString(time.charAt(1))));
        digits.add(Integer.parseInt(Character.toString(time.charAt(3))));
        digits.add(Integer.parseInt(Character.toString(time.charAt(4))));        
    
        recur(digits, 0, hour, min, select);
        return String.format("%02d", h) + ":" + String.format("%02d", m);
    }
    
    public void recur(Set<Integer> digits, int idx, int h1, int m1, int[] select) {
        if(idx == 4) {
            int h2 = select[0] * 10 + select[1];
            int m2 = select[2] * 10 + select[3];
            if(h1 > 23 || h2 > 23 || m1 > 59 || m2 > 59) return;

            int delta = time_diff(h1, m1, h2, m2);
            if(delta != 0 && delta < diff) {
                diff = delta;
                h = h2;
                m = m2;
            }
            return;
        }
        for(int digit : digits) {
            // Select digits[i] to be idx th digit in new time string
            select[idx] = digit;
            recur(digits, idx + 1, h1, m1, select);   
        }
    }
    
    /*
        How many minutes away from h1:m1 to h2:m2
    */
    public int time_diff(int h1, int m1, int h2, int m2) {
        if(h1 == h2 && m1 < m2) return m2 - m1;
        else if(h1 < h2) {
            return 60 * (h2 - h1 - 1) + (60 - m1) + m2;
        }
        else {
            int t = 60 * (23 - h1 - 1) + (60 - m1) + 59;
            return t + 60 * h2 + m2;
        }
    }
}