难度: Medium
给你一个二进制串 s （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。
请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。
由于答案可能很大，请将它对 10^9 + 7 取余后返回。
示例 1：
输入：s = "10101" 输出：4 解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。 "1|010|1" "1|01|01" "10|10|1" "10|1|01"
示例 2：
输入：s = "1001" 输出：0
示例 3：
输入：s = "0000" 输出：3 解释：总共有 3 种分割 s 的方法。 "0|0|00" "0|00|0" "00|0|0"
示例 4：
输入：s = "100100010100110" 输出：12
提示：
s[i] == '0' 或者 s[i] == '1'3 <= s.length <= 10^5运行时间: 56 ms
内存: 16.7 MB
class Solution:
def numWays(self, s: str) -> int:
news = [i for i,num in enumerate(s) if num=='1']
k = len(news)
if k%3:return 0
if not k:return (len(s)-1)*(len(s)-2)//2%1000000007
return (news[k//3]-news[k//3-1])*(news[k//3*2]-news[k//3*2-1])%1000000007
首先，我们需要统计字符串中'1'的总数。如果'1'的总数不能被3整除，那么不可能等分成三个部分，直接返回0。如果没有'1'，即字符串全为'0'，则可以在任何两个'0'之间切割来形成三个部分，计算方式是组合数C(n-1, 2)，其中n是字符串的长度。如果'1'的数量可以被3整除，我们计算每个部分应含有的'1'的数量，然后找到这些'1'在原字符串中的确切位置。具体地，我们需要计算第1/3和第2/3位置的'1'之间，以及第2/3和第3/3位置的'1'之间的'0'的数量，这些'0'可以灵活地分配到相邻的部分中。最后，将这两个间隔的长度相乘即可得到分割方案的总数。
时间复杂度: O(n)
空间复杂度: O(n)
# 添加了详细注释的代码
class Solution:
def numWays(self, s: str) -> int:
# 创建一个列表，记录所有'1'的索引位置
news = [i for i, num in enumerate(s) if num == '1']
# 计算'1'的总数
k = len(news)
# 如果'1'的数量不能被3整除，直接返回0
if k % 3: return 0
# 如果没有'1'，计算全为'0'的分割方案数，使用组合数公式C(n-1, 2)
if not k: return (len(s) - 1) * (len(s) - 2) // 2 % 1000000007
# 计算可以移动的'0'的数量，这些'0'决定了分割的灵活性
return (news[k // 3] - news[k // 3 - 1]) * (news[k // 3 * 2] - news[k // 3 * 2 - 1]) % 1000000007
在全为'0'的字符串中，没有'1'来限制分割点的位置，因此任何两个位置都可以作为分割点来将字符串分为三部分。字符串长度为n时，我们需要选择两个位置来放置分割点，这些位置从字符串的第一个字符后到最后一个字符前的n-1个位置中选取。这是一个从n-1个元素中选择2个的组合问题，因此使用组合数公式C(n-1, 2)来计算分割方案的总数。
在Python代码中，通过遍历字符串的每个字符并检查它是否为'1'，然后记录其索引，可以确保不会漏掉任何一个'1'。这种方法包括检查字符串的每个位置，无论'1'是否位于字符串的边界。因此，即使'1'位于字符串的开头或结尾，它们也会被正确地统计和记录。
如果'1'的数量可以被3整除，意味着可以将'1'平均分配到三个部分中。在这种情况下，关键是要确定每部分的'1'之间可以有多少个'0'，因为这些'0'可以灵活地分配到相邻的部分中，从而形成不同的分割方案。计算两个分割点之间的'0'数量可以让我们知道每两个'1'集团之间有多少空间可以用来调整分割点的位置，从而影响到分割方案的总数。这种计算方法能够准确地反映分割点之间的灵活性，从而正确地计算出所有可能的分割方案。
在代码中，通过计算第1/3和第2/3位置的'1'的索引时，我们确保使用了正确的索引计算公式来避免数组越界。例如，使用`news[k // 3]`和`news[k // 3 - 1]`来找到第1/3位置的'1'的索引。这种方法确保在访问数组时索引是有效的，因为通过整数除法`k // 3`计算的结果总是在有效索引范围内。同时，由于'1'的数量已知可以被3整除，所以这些计算不会导致越界错误。