Giả sử chúng ta có hai chuỗi số s và t, chúng ta muốn chuyển từ chuỗi s sang t bằng phép toán sau bất kỳ số lần nào:1. Chọn một chuỗi con không rỗng trong s và sắp xếp nó ở vị trí để các ký tự theo thứ tự tăng dần. Chúng ta phải kiểm tra xem có thể biến chuỗi s thành chuỗi t hay không.
Vì vậy, nếu đầu vào là s ="95643" t ="45963", thì đầu ra sẽ là True vì chúng ta có thể biến đổi s thành t bằng cách sử dụng như "95643" -> "95463" -> "45963".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
địa điểm:=một bản đồ trong đó loại giá trị mặc định là danh sách
-
đối với tôi trong phạm vi kích thước s đến 0, hãy thực hiện
-
key:=s [i] as integer
-
điền tôi vào cuối các vị trí [key]
-
-
cho mỗi e trong t, làm
-
key:=e as integer
-
nếu địa điểm [key] trống, thì
-
trả về Sai
-
-
i:=phần tử cuối cùng của địa điểm [key]
-
đối với j trong phạm vi từ 0 đến khóa - 1, thực hiện
-
nếu địa điểm [j] không trống và phần tử cuối cùng của địa điểm [j]
-
trả về Sai
-
-
-
xóa phần tử cuối cùng khỏi các địa điểm [key]
-
-
-
trả về True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để 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