[leetcode] 1573. Number of Ways to Split a String

[leetcode] 1573. Number of Ways to Split a String

Description

Given a binary string s (a string consisting only of '0’s and '1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "10101"Output: 4Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'."1|010|1""1|01|01""10|10|1""10|1|01"

Example 2:

Input: s = "1001"Output: 0

Example 3:

Input: s = "0000"Output: 3Explanation: There are three ways to split s in 3 parts."0|0|00""0|00|0""00|0|0"

Example 4:

Input: s = "100100010100110"Output: 12

Constraints:

3 <= s.length <= 10^5s[i] is ‘0’ or ‘1’.

分析

题目的意思是：给定一个字符串，分为3部分，每部分1的数量相同。求有多少种划分方式。要分两种情况考虑，第一种是全0的情况，用数学的方法可以计算出来，见代码；另一种是统计1的个数，除以3得到每个分段的1的个数，统计第一段和第三段的组合数目，然后乘积就是最终的答案了。

代码

class Solution: def numWays(self, s: str) -> int: cnt=0 n=len(s) for ch in s: if(ch=='1'): cnt+=1 if(cnt==0): return (n-1)*(n-2)//2%(10**9+7) if(cnt%3!=0): return 0 cnt2=0 l=0 r=0 t=cnt//3 for ch in s: if(ch=='1'): cnt2+=1 if(cnt2==t): l+=1 if(cnt2==2*t): r+=1 return l*r%(10**9+7)

参考文献

​​[LeetCode] 花花酱 LeetCode 1573. Number of Ways to Split a String - 刷题找工作 EP354​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。