Description#
You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).
The valid times are those inclusively between 00:00 and 23:59.
Return the latest valid time you can get from time by replacing the hidden digits.
Example 1:
Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.
Example 2:
Input: time = "0?:3?"
Output: "09:39"
Example 3:
Input: time = "1?:22"
Output: "19:22"
Constraints:
time is in the format hh:mm.- It is guaranteed that you can produce a valid time from the given string.
Solutions#
Solution 1: Greedy#
We process each digit of the string in order, following these rules:
- First digit: If the value of the second digit is determined and falls within the range $[4, 9]$, then the first digit can only be $1$. Otherwise, the first digit can be up to $2$.
- Second digit: If the value of the first digit is determined and is $2$, then the second digit can be up to $3$. Otherwise, the second digit can be up to $9$.
- Third digit: The third digit can be up to $5$.
- Fourth digit: The fourth digit can be up to $9$.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def maximumTime(self, time: str) -> str:
t = list(time)
if t[0] == '?':
t[0] = '1' if '4' <= t[1] <= '9' else '2'
if t[1] == '?':
t[1] = '3' if t[0] == '2' else '9'
if t[3] == '?':
t[3] = '5'
if t[4] == '?':
t[4] = '9'
return ''.join(t)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public String maximumTime(String time) {
char[] t = time.toCharArray();
if (t[0] == '?') {
t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';
}
if (t[1] == '?') {
t[1] = t[0] == '2' ? '3' : '9';
}
if (t[3] == '?') {
t[3] = '5';
}
if (t[4] == '?') {
t[4] = '9';
}
return new String(t);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
string maximumTime(string time) {
if (time[0] == '?') {
time[0] = (time[1] >= '4' && time[1] <= '9') ? '1' : '2';
}
if (time[1] == '?') {
time[1] = (time[0] == '2') ? '3' : '9';
}
if (time[3] == '?') {
time[3] = '5';
}
if (time[4] == '?') {
time[4] = '9';
}
return time;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func maximumTime(time string) string {
t := []byte(time)
if t[0] == '?' {
if t[1] >= '4' && t[1] <= '9' {
t[0] = '1'
} else {
t[0] = '2'
}
}
if t[1] == '?' {
if t[0] == '2' {
t[1] = '3'
} else {
t[1] = '9'
}
}
if t[3] == '?' {
t[3] = '5'
}
if t[4] == '?' {
t[4] = '9'
}
return string(t)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* @param {string} time
* @return {string}
*/
var maximumTime = function (time) {
const t = Array.from(time);
if (t[0] === '?') {
t[0] = t[1] >= '4' && t[1] <= '9' ? '1' : '2';
}
if (t[1] === '?') {
t[1] = t[0] == '2' ? '3' : '9';
}
if (t[3] === '?') {
t[3] = '5';
}
if (t[4] === '?') {
t[4] = '9';
}
return t.join('');
};
|
