Easy to understand Java solution [Permutations]


  • 0
    S

    This solutions determines all the possible string permutations that can be computed from the input string and then calculates the delta (from the input time) for each of those permutations. If the computed delta is lower than the minimum delta, the computed delta is stored as the new minimum as well as the string that produced that delta.

    class Solution {
        
        int minDelta = Integer.MAX_VALUE;
        String result = "";
        
        public String nextClosestTime(String time) {
            Set<Character> nums = new HashSet<>();
            // Load individual numbers into a set that we can use later...
            for (int i = 0; i < time.length(); i++) {
                char c = time.charAt(i);
                if (Character.isDigit(c)) {
                    nums.add(c);
                }
            }
            
            // Search for the shortest delta
            searchMinDelta("", nums, time);
    
            return result;
        }
        
        private void searchMinDelta(String cand, Set<Character> nums, String time) {
            // If we have a string of length 5 we have a candidate for a result
            if (cand.length() == 5) {
                if (isValid(cand)) {
                    // Calculate the delta and see if it is the new minimum
                    int delta = calculateDelta(cand, time);
                    if (delta < minDelta) {
                        // If so, overwrite the min and result
                        minDelta = delta;
                        result = cand;
                    }
                }            
                return;
            }
            
            // If the length is 2 we need to add our hour/minute separator
            if (cand.length() == 2) {
                cand += ":";
            }
            
            // Recursively call this function to find all the permutations of the potential times
            for (Character numChar : nums) {
                searchMinDelta(cand + numChar, nums, time);
            }
        }
        
        // Determines if the string is a valid time representation
        private boolean isValid(String s) {
            String[] parts = s.split(":");
            int hours = Integer.parseInt(parts[0]);
            int minutes = Integer.parseInt(parts[1]);
            return hours < 24 && minutes < 60; 
        }
        
        private int calculateDelta(String cand, String time) {
            int candMins = calculateMins(cand);
            int timeMins = calculateMins(time);
            
            int diff = candMins - timeMins;
            
            // Candidate is ahead of the current time
            if (candMins > timeMins) {
                return diff;
            // Candidate is behind the current time. Calculate delta for next day.
            } else {
                return (24*60) + diff;
            }
        }
        
        // Calculates the minutes elapsed in a day
        private int calculateMins(String time) {
            String[] parts = time.split(":");
            int hours = Integer.parseInt(parts[0]);
            int minutes = Integer.parseInt(parts[1]);
            return (hours * 60) + minutes;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.