Worker Hour Schedules
MediumBacktracking · SalesForce
An employee's weekly schedule is a 7-character string pattern, one character per day. A digit is the number of hours already fixed for that day, and ? marks a day whose hours are still unknown.
Replace every ? with a digit from 0 to day_hours (inclusive) so that the seven digits add up to exactly work_hours.
Return all valid completed schedules as strings, sorted in ascending lexicographic order. Return an empty list if none exists.
Example 1
- Input:
- work_hours = 24, day_hours = 8, pattern = "08??840"
- Output:
- ["0804840", "0813840", "0822840", "0831840", "0840840"]
- Explanation
- The fixed digits sum to 20, so the two
?days must add up to 4. The five ways are(0, 4),(1, 3),(2, 2),(3, 1)and(4, 0), listed in ascending order.
Example 2
- Input:
- work_hours = 15, day_hours = 4, pattern = "44?1?00"
- Output:
- ["4421400", "4431300", "4441200"]
- Explanation
- The fixed digits sum to 9, so the unknown days need 6 hours. Each day is capped at 4, which leaves only
(2, 4),(3, 3)and(4, 2).
Example 3
- Input:
- work_hours = 30, day_hours = 3, pattern = "1?2?3?3"
- Output:
- []
- Explanation
- The fixed digits sum to 9, so the three unknown days would need 21 hours, but at most
3 * 3 = 9fit.
Constraints
pattern.length== 7patterncontains only the digits0-8and?, and every fixed digit is at mostday_hours- 0 ≤
day_hours≤ 8 - 0 ≤
work_hours≤ 56 - The answer contains at most 104 schedules