Chương trình tìm một số cách để tách một chuỗi trong Python

Giả sử chúng ta có một chuỗi nhị phân s, chúng ta có thể tách s thành 3 chuỗi không rỗng s1, s2, s3 sao cho (s1 nối s2 nối s3 =s). Chúng ta phải tìm số cách có thể chia s sao cho số ký tự '1' giống nhau trong s1, s2 và s3. Câu trả lời có thể rất lớn vì vậy hãy trả lại câu trả lời mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là s =​​"11101011", thì đầu ra sẽ là 2 vì chúng ta có thể chia chúng như "11 | 1010 | 11" và "11 | 101 | 011".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• count:=đếm số lượng 1 trong s
• m:=10 ^ 9 + 7
• ans:=một mảng có kích thước 2 và điền bằng 0
• nếu số lượng mod 3 không giống 0, thì
  • trả về 0
• ngược lại khi số đếm bằng 0 thì
  • return (nCr trong đó n là kích thước của s -1 và r là 2) mod m
• trái:=0
• right:=kích thước của s - 1
• cum_s:=0, cum_e:=0
• while cum_s <=quotient of count / 3 or cum_e <=quotient of count / 3, do
  • nếu s [left] giống với "1", thì
    • cum_s:=cum_s + 1
  • nếu s [right] giống như "1", thì
    • cum_e:=cum_e + 1
  • nếu cum_s giống với thương của số đếm / 3, thì
    • ans [0]:=ans [0] + 1
  • nếu cum_e giống với thương của số đếm / 3, thì
    • ans [1]:=ans [1] + 1
  • left:=left + 1
  • right:=right - 1
• return (ans [0] * ans [1]) mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

"11101011"

Đầu ra

2