โปรแกรมค้นหาสตริงที่ดีจากสตริงที่กำหนดใน Python

สมมติว่าเรามีสตริง s ที่มีตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ เราจะพิจารณาว่าสตริงเป็นสตริงที่ดีซึ่งไม่มีอักขระสองตัวที่อยู่ติดกัน s[i] และ s[i + 1] โดยที่ −

• 0 <=i <=ขนาดของ s - 2

• s[i] เป็นตัวพิมพ์เล็กและ s[i + 1] เป็นตัวอักษรเดียวกันแต่เป็นตัวพิมพ์ใหญ่หรือกลับกัน

ในการแปลงสตริงเป็นสตริงที่ดี เราสามารถเลือกอักขระสองตัวที่อยู่ติดกันซึ่งทำให้สตริงไม่ดีและลบออก เราจะดำเนินการตามขั้นตอนนี้ต่อไปจนกว่าสตริงจะดี (สตริงว่างอาจเป็นสตริงที่ดีได้) เราต้องตามหาเชือกหลังจากที่ทำให้มันดี

ดังนั้น หากอินพุตเป็นแบบ s ="popPpulaBbr" ผลลัพธ์จะเป็น "ยอดนิยม" เพราะในตอนแรก อาจมีการลบ "p ^P " หรือ "P_p " และลบ "Bb"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• res :=รายการใหม่

• สำหรับแต่ละอักขระ ch ใน s ทำ

  • หาก res ไม่ว่างเปล่าและองค์ประกอบสุดท้ายใน res เหมือนกับ ch ไม่ว่าในกรณีใด ๆ บนหรือล่าง

    • ลบองค์ประกอบสุดท้ายออกจาก res

  • มิฉะนั้น

    • ใส่ ch ต่อท้าย res

• เข้าร่วมแต่ละองค์ประกอบที่มีอยู่ใน res แล้วส่งคืน

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s):
   res = []
   for ch in s:
      if res and res[-1] != ch and res[-1].lower() == ch.lower():
         res.pop()
      else:
         res.append(ch)
   return ''.join(res)

s = "popPpulaBbr"
print(solve(s))

อินพุต

"popPpulaBbr"

ผลลัพธ์

popular