What pattern does Largest Time for Given Digits use?

This problem primarily uses backtracking search with pruning, exploring permutations of digits while skipping invalid hour or minute sequences.

Can I solve Largest Time for Given Digits without backtracking?

Yes, you can generate all 24 permutations directly and filter valid times, but backtracking with pruning is more efficient and matches the intended pattern.

How do I handle leading zeros in HH:MM format?

Always format hours and minutes as two digits, using leading zeros when necessary, e.g., 03:07 instead of 3:7.

What if no valid 24-hour time can be formed?

Return an empty string to indicate that no permutation of the digits satisfies the 24-hour time constraints.

Does pruning improve performance in this problem?

Yes, pruning eliminates impossible hour or minute combinations early, reducing the number of permutations explored and simplifying the search for the maximum valid time.

#949

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

给定数字能组成的最大时间

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。 24 小时格式为 "HH:MM" ，其中 HH 在 00 到 23 之间， MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ，而最大的是 23:59 。从 00:00 （午夜）开始算起，过得越久，…

数组字符串回溯枚举

题目描述

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

24 小时格式为 "HH:MM" ，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ，而最大的是 23:59 。从 00:00 （午夜）开始算起，过得越久，时间越大。

以长度为 5 的字符串，按 "HH:MM" 格式返回答案。如果不能确定有效时间，则返回空字符串。

示例 1：

输入：arr = [1,2,3,4]
输出："23:41"
解释：有效的 24 小时制时间是 "12:34"，"12:43"，"13:24"，"13:42"，"14:23"，"14:32"，"21:34"，"21:43"，"23:14" 和 "23:41" 。这些时间中，"23:41" 是最大时间。

示例 2：

输入：arr = [5,5,5,5]
输出：""
解释：不存在有效的 24 小时制时间，因为 "55:55" 无效。

示例 3：

输入：arr = [0,0,0,0]
输出："00:00"

示例 4：

输入：arr = [0,0,1,0]
输出："10:00"

提示：

arr.length == 4
0 <= arr[i] <= 9

lightbulb

解题思路

方法一：暴力枚举

我们可以枚举所有的 4 个数字的排列，然后判断每个排列是否满足题目要求，如果满足则更新答案。

时间复杂度 $O(4^3)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def largestTimeFromDigits(self, arr: List[int]) -> str:
        cnt = [0] * 10
        for v in arr:
            cnt[v] += 1
        for h in range(23, -1, -1):
            for m in range(59, -1, -1):
                t = [0] * 10
                t[h // 10] += 1
                t[h % 10] += 1
                t[m // 10] += 1
                t[m % 10] += 1
                if cnt == t:
                    return f'{h:02}:{m:02}'
        return ''

speed

复杂度分析

指标	值
时间	complexity is O(1) since the number of digit permutations is fixed at 4! = 24, and space complexity is also O(1) for storing permutations and tracking the maximum time. Pruning reduces unnecessary exploration, making backtracking efficient even though the theoretical complexity is constant due to fixed input size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate attempts all permutations without pruning, showing incomplete backtracking strategy.
question_mark
Candidate correctly identifies pruning opportunities for invalid hours and minutes early in recursion.
question_mark
Candidate efficiently returns the latest valid time, demonstrating understanding of enumeration with constraints.

warning

常见陷阱

外企场景

error
Failing to prune sequences that cannot form valid hours or minutes, leading to unnecessary recursion.
error
Incorrectly formatting time, e.g., missing leading zeros for hours or minutes.
error
Assuming any permutation of digits forms a valid 24-hour time, ignoring constraints for HH and MM ranges.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the earliest valid 24-hour time instead of the latest using the same digits.
arrow_right_alt
Determine the latest valid 12-hour time with AM/PM from four digits, requiring additional constraints.
arrow_right_alt
Handle arrays of 6 digits and find the latest valid time including seconds in HH:MM:SS format.

help

常见问题

外企场景

继续练习

#816 模糊坐标 #691 贴纸拼词 #1239 串联字符串的最大长度