สมมติว่าเรามีสตริงไบนารี s เราสามารถลบตัวอักษรสองตัวที่อยู่ติดกันได้หากต่างกัน สุดท้าย เราต้องหาความยาวของสตริงที่เล็กที่สุดที่เราหาได้ หากเราสามารถดำเนินการนี้กี่ครั้งก็ได้ตามต้องการ
ดังนั้น หากอินพุตเป็น s ="1100011" ผลลัพธ์จะเป็น 1 เนื่องจากหลังจากลบ "10" เราจะได้ "10011" จากนั้นให้ลบ "10" อีกครั้ง จะเป็น "011" จากนั้นจึงลบ "01 " มันจะเหลือ 1.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- stack :=รายการใหม่
- สำหรับแต่ละ c ใน s ทำ
- ถ้า stack ว่างหรือด้านบนของ stack เหมือนกับ c แล้ว
- ดัน c ลงในสแต็ก
- มิฉะนั้นเมื่อด้านบนของ stack ไม่เหมือนกับ c แล้ว
- องค์ประกอบป๊อปจากสแต็ก
- ถ้า stack ว่างหรือด้านบนของ stack เหมือนกับ c แล้ว
- คืนจำนวนองค์ประกอบในกอง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, s):
stack = []
for c in s:
if not stack or stack[-1] == c:
stack.append(c)
elif stack[-1] != c:
stack.pop()
return len(stack)
ob = Solution() print(ob.solve("1100011")) อินพุต
"1100011"
ผลลัพธ์
1
