ลบตัวอักษรซ้ำติดกันในสตริง Python

ให้สตริง S ตัวพิมพ์เล็ก ทำการลบตัวอักษรซ้ำติดกัน (adjacent duplicates) ซ้ำๆ จนไม่มีซ้ำติดกันเหลือ คืนสตริงผลลัพธ์

ตัวอย่าง: "abbacaca" → ลบ "bb" ได้ "aacaca" → ลบ "aa" ได้ "caca" (จบ)

ขั้นตอนการแก้ปัญหา (Stack)

1. สร้าง stack ว่าง st ตั้ง i = 0
2. วนลูป while i < len(S):
   • ถ้า stack ไม่ว่าง และ st[-1] == S[i]: pop stack, i += 1
   • มิฉะนั้น: push S[i] เข้า stack, i += 1
3. รวม stack เป็นสตริงคืนค่า

ตัวอย่างโค้ด

class Solution(object):
    def removeDuplicates(self, S):
        st = []
        i = 0
        while i < len(S):
            if len(st) != 0 and st[-1] == S[i]:
                i += 1
                st.pop(-1)
            else:
                st.append(S[i])
                i += 1
        return "".join(i for i in st)

ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

อินพุต

"abbacaca"

เอาต์พุต

"caca"

วิธีแก้แบบ Pythonic (ใช้ list เป็น stack)

def removeDuplicates(S):
    stack = []
    for ch in S:
        if stack and stack[-1] == ch:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)