โปรแกรมค้นหาวิธีแยกสตริงใน Python . หลายวิธี

สมมติว่าเรามีสตริงไบนารีที่เราสามารถแยก s ออกเป็น 3 สตริงที่ไม่ว่าง s1, s2, s3 เช่นนั้น (s1 ต่อ s2 ต่อ s3 =s) เราต้องหาจำนวนวิธีที่จะแยก s เพื่อให้จำนวนอักขระ '1' เท่ากันใน s1, s2 และ s3 คำตอบอาจมีขนาดใหญ่มาก ให้ส่งคืน mod 10^9+7

ดังนั้น หากอินพุตเป็นเหมือน s ="11101011" ผลลัพธ์จะเป็น 2 เพราะเราสามารถแยกออกเป็น "11 | 1010 | 11" และ "11 | 101 | 011"

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

• นับ :=นับจำนวน 1 วินาทีใน s
• ม :=10^9 + 7
• ans :=อาร์เรย์ขนาด 2 และเติม 0
• ถ้าการนับ mod 3 ไม่เหมือนกับ 0 แล้ว
  • คืน 0
• มิฉะนั้นเมื่อการนับเท่ากับ 0 แล้ว
  • ผลตอบแทน (nCr โดยที่ n คือขนาดของ s -1 และ r คือ 2) mod m
• ซ้าย :=0
• ขวา :=ขนาด s - 1
• cum_s :=0, cum_e :=0
• ในขณะที่ cum_s <=ผลหารของการนับ/3 หรือ cum_e <=ผลหารของการนับ/3 ทำ
  • ถ้า s[left] เหมือนกับ "1" แล้ว
    • cum_s :=cum_s + 1
  • ถ้า s[right] เหมือนกับ "1" แล้ว
    • cum_e :=cum_e + 1
  • ถ้า cum_s เหมือนกับผลหารของ count/3 แล้ว
    • ans[0] :=ans[0] + 1
  • ถ้า cum_e เหมือนกับผลหารของ count/3 แล้ว
    • ans[1] :=ans[1] + 1
  • ซ้าย :=ซ้าย + 1
  • ขวา :=ขวา - 1
• return (ans[0]*ans[1]) mod m

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

ตัวอย่าง

def solve(s):
   count = s.count("1")
   m = 10**9 + 7
   ans = [0, 0]
   if count % 3 != 0:
      return 0
   elif count == 0:
      return comb(len(s)-1,2) % m
   left = 0
   right = len(s)-1
   cum_s = 0
   cum_e = 0
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s+=1
      if s[right] == "1":
         cum_e+=1
      if cum_s == count//3:
         ans[0]+=1
      if cum_e == count//3:
         ans[1]+=1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m
s = "11101011"
print(solve(s))

อินพุต

"11101011"

ผลลัพธ์

2