Cho hai chuỗi số s và t. Cho phép chọn chuỗi con không rỗng của s và sắp xếp tăng dần tại chỗ. Kiểm tra có thể biến đổi s thành t không.
Ví dụ: s = "95643", t = "45963", đầu ra = True (95643 → 95463 → 45963).
Giải pháp
Greedy từ phải sang trái: duyệt t, tìm ký tự tương ứng trong s bên trái, đảm bảo không có ký tự nhỏ hơn bị chặn:
- places := map mặc định list
- Với i từ len(s)-1 xuống 0: key = int(s[i]), places[key].append(i)
- Với mỗi e trong t:
- key = int(e)
- Nếu places[key] rỗng: trả về False
- i := places[key][-1]
- Với j từ 0 đến key-1: nếu places[j] không rỗng và places[j][-1] < i: trả về False
- Xóa places[key][-1]
- Trả về True
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
from collections import defaultdict
def solve(s, t):
places = defaultdict(list)
for i in reversed(range(len(s))):
key = int(s[i])
places[key].append(i)
for e in t:
key = int(e)
if not places[key]:
return False
i = places[key][-1]
for j in range(key):
if places[j] and places[j][-1] < i:
return False
places[key].pop()
return True
s = "95643"
t = "45963"
print(solve(s, t))
Đầu vào
"95643", "45963"
Đầu ra
True