Sometimes it is OK to try all permutations

Many times in computer science we're taught to avoid permutations at all costs. This is actually a myth. Permutation is a powerful tool which can be safely applied when the conditions are right. For example, the following problem asks for the total number of valid permutations for a given string to become a valid time. Analyzing the string, you can see that the total possibilities are four question marks which would then entail 10^4, which is 10,000. You can safely try them all using a simple backtracking algorithm, together with StringBuilder for easy manipulation of the string. Code is below, cheers, ACC.

Number of Valid Clock Times - LeetCode

2437. Number of Valid Clock Times

Easy

You are given a string of length 5 called time, representing the current time on a digital clock in the format "hh:mm". The earliest possible time is "00:00" and the latest possible time is "23:59".

In the string time, the digits represented by the ? symbol are unknown, and must be replaced with a digit from 0 to 9.

Return an integer answer, the number of valid clock times that can be created by replacing every ? with a digit from 0 to 9.

 

Example 1:

Input: time = "?5:00"
Output: 2
Explanation: We can replace the ? with either a 0 or 1, producing "05:00" or "15:00". Note that we cannot replace it with a 2, since the time "25:00" is invalid. In total, we have two choices.

Example 2:

Input: time = "0?:0?"
Output: 100
Explanation: Each ? can be replaced by any digit from 0 to 9, so we have 100 total choices.

Example 3:

Input: time = "??:??"
Output: 1440
Explanation: There are 24 possible choices for the hours, and 60 possible choices for the minutes. In total, we have 24 * 60 = 1440 choices.

 

Constraints:

• time is a valid string of length 5 in the format "hh:mm".
• "00" <= hh <= "23"
• "00" <= mm <= "59"
• Some of the digits might be replaced with '?' and need to be replaced with digits from 0 to 9.

public int CountTime(string time)
{
    StringBuilder sbTime = new StringBuilder(time);
    int retVal = 0;
    CountTime(sbTime, 0, ref retVal);
    return retVal;
}

private void CountTime(StringBuilder time,
                        int index,
                        ref int countValid)
{
    if (index >= time.Length)
    {
        countValid = IsValidTime(time.ToString()) ? countValid + 1 : countValid;
        return;
    }

    if (time[index] != '?')
    {
        CountTime(time, index + 1, ref countValid);
    }
    else
    {
        for (int i = 0; i < 10; i++)
        {
            time[index] = (char)((int)'0' + i);
            CountTime(time, index + 1, ref countValid);
            time[index] = '?';
        }
    }
}

private bool IsValidTime(string time)
{
    string[] parts = time.Split(':');

    int hour = Int32.Parse(parts[0]);
    int minutes = Int32.Parse(parts[1]);

    if (hour < 0 || hour > 23) return false;
    if (minutes < 0 || minutes > 59) return false;
    return true;
}