DI String Match (จับคู่สตริง I/D) ใน Python

โจทย์: ให้สตริง S ประกอบด้วย 'I' (Increase) และ 'D' (Decrease) หา Permutation ของ [0, 1, ..., N] ที่ทำให้: S[i]=='I' → A[i] < A[i+1], S[i]=='D' → A[i] > A[i+1]

Input/Output

Input:  "IDID"
Output: [0, 4, 1, 3, 2]

อัลกอริทึม (Two Pointers / Greedy)

1. สร้าง Array A = [0, 1, ..., N]
2. ใช้ 2 Pointer: Low = 0, High = N
3. อ่าน S ทีละตัว: 'I' → ใช้ Low แล้ว Low++, 'D' → ใช้ High แล้ว High--
4. ท้ายสุดใส่ค่าที่เหลือ (Low == High)

ตัวอย่างโค้ด (One-liner)

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"))

ผลลัพธ์

[0, 4, 1, 3, 2]

การอธิบาย One-liner

• (j == 'I') - 1: 'I' → True(1)-1=0 (Pop index 0 = Low), 'D' → False(0)-1=-1 (Pop index -1 = High)
• A.pop(0) ดึงค่าน้อยที่สุด, A.pop(-1) ดึงค่ามากที่สุด
• เหลือ 1 ค่าใน A ท้ายสุด → + A

วิธีเขียนอ่านง่าย (Explicit)

def diStringMatch(self, S):
    low, high = 0, len(S)
    result = []
    for ch in S:
        if ch == 'I':
            result.append(low)
            low += 1
        else:
            result.append(high)
            high -= 1
    result.append(low)  # low == high
    return result

ทั้งสองวิธีให้ผลลัพธ์เดียวกัน วิธี Explicit อ่านง่ายกว่าและ Debug ง่ายกว่า