Giả sử chúng ta có một chuỗi S chỉ chứa "I" (để biểu thị tăng) hoặc "D" (để biểu thị giảm), cho N =kích thước của S. Chúng ta phải trả về bất kỳ hoán vị A nào của [0, 1, ... , N] sao cho mọi i trong phạm vi 0, ..., N-1 -
- Nếu S [i] là "I" thì A [i]
- Ngược lại khi S [i] là "D" thì A [i]> A [i + 1]
Vì vậy, nếu đầu vào giống như "IDID", thì đầu ra sẽ là [0,4,1,3,2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- A:=một danh sách từ 0 đến N trong đó N là kích thước của S.
- res =một danh sách trống
- đối với mỗi phần tử j trong S, thực hiện
- nếu j là I, thì xóa phần tử cuối cùng khỏi A và chèn vào res
- nếu không, hãy xóa phần tử đầu tiên của A và chèn vào res
- trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def diStringMatch(self, S):
A=[i for i in range(len(S)+1)]
return [A.pop((j=='I')-1) for j in S]+A
ob = Solution()
print(ob.diStringMatch("IDID")) Đầu vào
"IDID"
Đầu ra
[0, 4, 1, 3, 2]