Python程式：查詢分割字串的方法數

假設我們有一個二進位制字串 s，我們可以將 s 分割成 3 個非空字串 s1、s2、s3，使得 (s1 連線 s2 連線 s3 = s)。我們需要找到 s 可以分割的方式數量，使得 s1、s2 和 s3 中字元 '1' 的數量相同。答案可能非常大，因此返回答案模 10^9+7。

所以，如果輸入類似 s = "11101011"，則輸出將為 2，因為我們可以將其分割為 "11 | 1010 | 11" 和 "11 | 101 | 011"。

為了解決這個問題，我們將遵循以下步驟

  • count := 計算 s 中 1 的數量
  • m := 10^9 + 7
  • ans := 一個大小為 2 的陣列，並填充 0
  • 如果 count 模 3 不等於 0，則
    • 返回 0
  • 否則，當 count 等於 0 時，則
    • 返回 (nCr，其中 n 是 s 的大小 -1，r 是 2) 模 m
  • left := 0
  • right := s 的大小 - 1
  • cum_s := 0, cum_e := 0
  • 當 cum_s <= count/3 的商 或 cum_e <= count/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
    • left := left + 1
    • right := right - 1
  • 返回 (ans[0]*ans[1]) 模 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

更新於: 2021年10月4日

343 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告