Number Of Valid Clock Times - Leetcode Solution

Problem Description:

Given a string of 4 digits, representing a time in the format "HH:MM", find all the valid time that can be formed by re-arranging the digits.

A valid time is a time that satisfies the following criteria:

• The hour part must be between 00 and 23 (inclusive).
• The minute part must be between 00 and 59 (inclusive).
• Both the hour and minute parts must consist of at least two digits, and any leading zeroes must be omitted.

Example Input: "19:38"

Example Output: ["19:38", "19:83", "38:19", "38:91", "81:39", "81:93", "91:38", "91:83"]

Solution:

This problem asks us to find all the valid times that can be formed by re-arranging the given input string. To approach this problem, we will need to break it down into smaller sub-problems. Let's see how we can do this:

1. We need to extract the digits from the given input string and store them in an array. We can do this by iterating over the string and converting each character to an integer.

2. Once we have extracted the digits, we need to generate all the possible permutations of these digits. We can use recursion to achieve this. At each step, we will choose one digit from the array and add it to the current permutation. We will then remove this digit from the array and call the recursive function on the remaining digits. We will continue this process until we have added all the digits to the current permutation.

3. For each valid permutation, we need to check if it represents a valid time. To do this, we will need to extract the hour and minute parts from the permutation and check if they are within the valid range.

4. If a permutation represents a valid time, we will add it to our output array.

Here is the Python code to implement the above approach:

class Solution:
    def __init__(self):
        self.output = []
        
    def permutation_helper(self, digits, current):
        if len(digits) == 0:
            self.output.append(current)
        else:
            for i in range(len(digits)):
                remaining_digits = digits[:i] + digits[i+1:]
                self.permutation_helper(remaining_digits, current + str(digits[i]))
    
    def isValidTime(self, time):
        hour = int(time[:2])
        minute = int(time[2:])
        return 0 <= hour <= 23 and 0 <= minute <= 59
    
    def permute(self, digits: str) -> List[str]:
        digits_array = [int(d) for d in digits]
        self.permutation_helper(digits_array, "")
        valid_times = []
        for time in self.output:
            if self.isValidTime(time):
                valid_times.append(time[:2] + ":" + time[2:])
        return valid_times

In this code, we define a class Solution that contains the three helper functions we discussed above: permutation_helper, isValidTime, and permute.

The permutation_helper function generates all the possible permutations of the digits using recursion. It takes in two parameters: digits (which is the remaining digits to be added to the current permutation) and current (which is the current permutation being generated).

The isValidTime function checks if a permutation represents a valid time by extracting the hour and minute parts and checking if they are within the valid range.

The permute function is the main function that calls the permutation_helper function and checks if each permutation is a valid time. It returns a list of all the valid times.

1