LeetCode 题解工作台
替换字符可以得到的最晚时间
给你一个字符串 s ，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。 12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11 ， MM 的取值范围为 00 至 59 。最早的时间为 00:00 ，最晚的时间为 11:59 。 你需要将 s 中…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · string·结合·enumeration
答案摘要
我们可以从大到小枚举所有的时间，其中小时 从 到 ，分钟 从 到 。对于每一个时间 ，我们检查是否满足 的每一位字符都与 的对应位置字符相等（如果 的对应位置字符不是 "?" 的话）。如果满足，那么我们就找到了答案，返回 。 时间复杂度 $O(h \times m)$，其中 $h = 12$, $m = 60$。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·enumeration 题型思路
题目描述
给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。
12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。
你需要将 s 中的 所有 "?" 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。
返回结果字符串。
示例 1：
输入： s = "1?:?4"
输出： "11:54"
解释： 通过替换 "?" 字符，可以得到的最晚12小时制时间是 "11:54"。
示例 2：
输入： s = "0?:5?"
输出： "09:59"
解释： 通过替换 "?" 字符，可以得到的最晚12小时制时间是 "09:59"。
提示：
s.length == 5s[2]是字符":"- 除
s[2]外，其他字符都是数字或"?" - 输入保证在替换
"?"字符后至少存在一个介于"00:00"和"11:59"之间的时间。
解题思路
方法一：枚举
我们可以从大到小枚举所有的时间，其中小时 从 到 ，分钟 从 到 。对于每一个时间 ，我们检查是否满足 的每一位字符都与 的对应位置字符相等（如果 的对应位置字符不是 "?" 的话）。如果满足，那么我们就找到了答案，返回 。
时间复杂度 ，其中 , 。空间复杂度 。
class Solution:
def findLatestTime(self, s: str) -> str:
for h in range(11, -1, -1):
for m in range(59, -1, -1):
t = f"{h:02d}:{m:02d}"
if all(a == b for a, b in zip(s, t) if a != "?"):
return t
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of string manipulation.
- question_mark
The interviewer may focus on efficiency or correctness of validation.
- question_mark
The problem may signal an interest in optimization strategies, like greedy algorithms.
常见陷阱
外企场景- error
Failing to check the bounds of valid hours and minutes when replacing '?' characters.
- error
Choosing incorrect digits when replacing '?' characters, leading to invalid times.
- error
Overcomplicating the problem by trying overly complex solutions when a greedy approach is sufficient.
进阶变体
外企场景- arrow_right_alt
Change the range of hours (e.g., 00-23) to test different time formats.
- arrow_right_alt
Introduce more '?' characters to increase the complexity.
- arrow_right_alt
Modify the problem to generate the earliest valid time instead of the latest.