สมมติว่าเรามีสตริง S ที่มีเฉพาะ "I" (เพื่อแสดงถึงการเพิ่มขึ้น) หรือ "D" (เพื่อแสดงถึงการลดลง) ให้ N =ขนาดของ S เราต้องคืนค่าการเรียงสับเปลี่ยน A ของ [0, 1, ... , N] เช่นนั้นสำหรับ i ทุกคนในช่วง 0, ..., N-1 −
- ถ้า S[i] คือ "I" ดังนั้น A[i]
- มิฉะนั้น เมื่อ S[i] คือ "D" แล้ว A[i]> A[i+1]
ดังนั้นหากอินพุตเป็นเหมือน "IDID" เอาต์พุตจะเป็น [0,4,1,3,2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- A :=รายการตั้งแต่ 0 ถึง N โดยที่ N คือขนาดของ S
- res =รายการว่าง
- สำหรับแต่ละองค์ประกอบ j ใน S ให้ทำ
- ถ้า j คือ I ให้ลบองค์ประกอบสุดท้ายจาก A แล้วแทรกลงใน res
- มิฉะนั้น ให้ลบองค์ประกอบแรกของ A แล้วแทรกลงใน res
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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")) อินพุต
"IDID"
ผลลัพธ์
[0, 4, 1, 3, 2]
