Cho thời gian dạng "hh:mm" 24h. Tìm thời gian gần nhất sau đó có thể tạo bằng cách tái sử dụng các chữ số đã cho (dùng lại không giới hạn lần).
Ví dụ: "03:15" → "03:30".
Giải thuật
- Thu thập 4 chữ số từ chuỗi đầu vào.
- Backtrack sinh tất cả thời gian hợp lệ (hh: 00-23, mm: 00-59) từ 4 chữ số đó.
- Sắp xếp danh sách thời gian hợp lệ.
- Tìm thời gian đầu vào trong danh sách, trả về thời gian tiếp theo; nếu là cuối cùng trả về thời gian đầu tiên (ngày kế).
Ví dụ minh họa
class Solution:
def solve(self, s):
use = [s[0], s[1], s[3], s[4]]
possible = set()
def backtrack(path):
nonlocal possible, use
if len(path) == 4:
possible.add(path[:2] + ":" + path[2:])
return
for p in use:
if not (len(path) == 0 and p > "2") and not (path == "2" and p > "3") and not (len(path) == 2 and p > "5"):
backtrack(path + p)
backtrack("")
possible = list(possible)
possible.sort()
for i in range(len(possible) - 1):
if possible[i] == s:
return possible[i+1]
return possible[0]
ob = Solution()
s = "03:15"
print(ob.solve(s))
Đầu vào
"03:15"
Đầu ra
03:30