题目描述

给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。

12 小时制时间格式为 "HH:MM"，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。

你需要将 s 中的 所有 "?" 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。

返回结果字符串。

样例

输入： s = "1?:?4"

输出： "11:54"

解释： 通过替换 "?" 字符，可以得到的最晚 12 小时制时间是 "11:54"。

输入： s = "0?:5?"

输出： "09:59"

解释： 通过替换 "?" 字符，可以得到的最晚 12 小时制时间是 "09:59"。

限制

• s.length == 5
• s[2] 是字符 ":"。
• 除 s[2] 外，其他字符都是数字或 "?"。
• 输入保证在替换 "?" 字符后至少存在一个介于 "00:00" 和 "11:59" 之间的时间。

算法

(思维题) $O(1)$

1. 逐一判定 ? 可以被替换的最大数字。
2. 如果 $s(0)$ 是 ?，则根据 $s(1)$ 的取值替换为 1 或 0。当 $s(1)$ 为 ?、0 或 1 时，$s(0)$ 可以替换为 1，其余情况都为 0。
3. 如果 $s(1)$ 是 ?，则根据 $s(0)$ 的取值替换为 9 或 0。
4. $s(3)$ 和 $s(4)$ 如果是 ?，则可以分别替换为 5 和 9。

时间复杂度

• 基于规则的判断，时间复杂度为 $O(1)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    string findLatestTime(string s) {
        if (s[0] == '?')
            s[0] = (s[1] == '?' || s[1] == '0' || s[1] == '1') ? '1' : '0';

        if (s[1] == '?')
            s[1] = s[0] == '0' ? '9' : '1';

        if (s[3] == '?')
            s[3] = '5';

        if (s[4] == '?')
            s[4] = '9';

        return s;
    }
};