寻找在 Python 中分割字符串的多种方法的程序

假设我们有一个二进制字符串 s,我们可以将 s 拆分为 3 个非空字符串 s1、s2、s3,使得 (s1 concatenate s2 concatenate s3 = s)。我们必须找到可以拆分 s 的方式的数量,以便在 s1、s2 和 s3 中字符“1”的数量相同。答案可能很大,所以返回答案 mod 10^9+7。

因此,如果输入类似于 s = "11101011",那么输出将为 2,因为我们可以将它们拆分为 "11 | 1010 | 11" 和 "11 | 101 | 011"。

为了解决这个问题,我们将按照以下步骤操作:

  • count := 计算 s 中 1 的数量

  • 米:= 10^9 + 7

  • ans := 一个大小为 2 并用 0 填充的数组

  • 如果 count mod 3 不等于 0,则

    • 返回 0

  • 否则当计数等于 0 时,则

    • return (nCr 其中 n 是 s -1 的大小,r 是 2) mod m

  • 左:= 0

  • 右 := s 的大小 - 1

  • cum_s := 0, cum_e := 0

  • 而 cum_s <= 商数/3 或 cum_e <= 商数/3,做

    • ans[1] := ans[1] + 1

    • ans[0] := ans[0] + 1

    • cum_e := cum_e + 1

    • cum_s := cum_s + 1

    • 如果 s[left] 与“1”相同,则

    • 如果 s[right] 与“1”相同,则

    • 如果 cum_s 与 count/3 的商相同,则

    • 如果 cum_e 与 count/3 的商相同,则

    • 左 := 左 + 1

    • 右 := 右 - 1

    • 返回 (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

    以上是 寻找在 Python 中分割字符串的多种方法的程序 的全部内容, 来源链接: utcz.com/z/331693.html

    回到顶部