โปรแกรมค้นหาวิธีที่ดีในการแยกสตริงโดยใช้ Python

สมมติว่าเรามีสตริง s ตอนนี้การแบ่งเรียกว่าการแบ่งที่ดีเมื่อเราสามารถแยก s เป็น 2 สตริงที่ไม่ว่าง p และ q โดยที่การต่อกันเท่ากับ s และจำนวนตัวอักษรที่แตกต่างกันใน p และ q เท่ากัน เราต้องหาจำนวนการแยกที่ดีที่เราสามารถทำได้

ดังนั้น หากอินพุตเป็น s ="xzzxyx" ผลลัพธ์จะเป็น 2 เนื่องจากมีการแยกหลายวิธี แต่ถ้าเราแยกเป็น ("xxz", "xyx") หรือ ("xzzx", "yx") ถ้าอย่างนั้นก็ดี

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

• ผลลัพธ์ :=0

• left :=mal ว่างสำหรับนับความถี่ของรายการ

• right :=นับความถี่ของตัวละครแต่ละตัวใน s

• สำหรับแต่ละ c ใน s ทำ

  • ซ้าย[c] :=ซ้าย[c] + 1

  • right[c] :=right[c] - 1

  • ถ้า right[c] เป็นศูนย์ แล้ว

    • เอาออกขวา[c]

  • ถ้าขนาดด้านซ้ายเท่ากับขนาดด้านขวาแล้ว

    • ผลลัพธ์ :=ผลลัพธ์ + 1

• ส่งคืนผลลัพธ์

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

ตัวอย่าง

from collections import Counter
def solve(s):
   result = 0
   left, right = Counter(), Counter(s)
   for c in s:
      left[c] += 1
      right[c] -= 1
      if not right[c]:
         del right[c]
      if len(left) == len(right):
         result += 1
   return result
s = "xxzxyx"
print(solve(s))

อินพุต

"xxzxyx"

ผลลัพธ์

2