Khớp chuỗi DI (DI String Match) trong Python

Giả sử ta có chuỗi S chỉ chứa "I" (tăng) hoặc "D" (giảm), N = độ dài S. Ta trả về bất kỳ hoán vị A nào của [0, 1, ..., N] sao cho với mọi i trong 0..N-1:

• Nếu S[i] là "I", thì A[i] < A[i+1]
• Ngược lại S[i] là "D", thì A[i] > A[i+1]

Ví dụ, đầu vào "IDID", đầu ra [0,4,1,3,2]

Giải quyết:

• A := list từ 0 đến N (N = len(S))
• res = list rỗng
• for each j in S, do
  • if j == 'I', xóa phần tử cuối A thêm vào res
  • ngược lại xóa phần tử đầu A thêm vào res
• return res

Xem triển khai:

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]