Medium

题目描述

给你一个二进制字符串 s，你可以将 s 分割成 3 个 非空 字符串 s1、s2 和 s3（s1 + s2 + s3 = s）。

返回分割 s 的方案数，使得 s1、s2 和 s3 中字符 ‘1’ 的数目相同。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：s = "10101"
输出：4
解释：有四种方法将 s 分割成含有 '1' 数目相同的三部分。
"1|010|1"
"1|01|01"  
"10|10|1"
"10|1|01"

示例 2：

输入：s = "1001"
输出：0

示例 3：

输入：s = "0000"
输出：3
解释：有三种方法将 s 分割成三部分。
"0|0|00"
"0|00|0"
"00|0|0"

提示：

  • 3 <= s.length <= 10^5
  • s[i] 是 ‘0’ 或 ‘1’

解题思路

这道题要求将二进制字符串分成三个非空部分，且每部分的'1’的个数相同。

分析思路：

  1. 特殊情况处理：如果字符串中没有'1’或'1’的总数不能被3整除，需要特殊处理。

  2. 全为0的情况：如果字符串全为'0’，任意分割都满足条件。对于长度为n的字符串，分成3个非空部分的方案数为C(n-1,2) = (n-1)(n-2)/2。

  3. 一般情况：设'1’的总数为count，那么每部分应该有count/3个'1’。关键是确定分割点的位置：

    • 第一个分割点：在第count/3个'1’之后到第(count/3+1)个'1’之前
    • 第二个分割点：在第(2count/3)个'1’之后到第(2count/3+1)个'1’之前

  4. 计算方案数：找到每个'1’的位置，计算两个分割区间的长度，方案数为两个长度的乘积。

算法步骤：

  1. 统计'1’的总数和位置
  2. 判断是否能等分成三部分
  3. 如果全为'0’，返回组合数
  4. 否则计算分割区间长度并求乘积

代码实现

class Solution {
public:
    int numWays(string s) {
        const int MOD = 1e9 + 7;
        int n = s.length();
        vector<int> ones;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                ones.push_back(i);
            }
        }
        
        int count = ones.size();
        
        if (count % 3 != 0) {
            return 0;
        }
        
        if (count == 0) {
            return (long long)(n - 1) * (n - 2) / 2 % MOD;
        }
        
        int target = count / 3;
        int first_end = ones[target - 1];
        int second_start = ones[target];
        int second_end = ones[2 * target - 1];
        int third_start = ones[2 * target];
        
        long long ways1 = second_start - first_end;
        long long ways2 = third_start - second_end;
        
        return ways1 * ways2 % MOD;
    }
};

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        ones = []
        
        for i in range(n):
            if s[i] == '1':
                ones.append(i)
        
        count = len(ones)
        
        if count % 3 != 0:
            return 0
        
        if count == 0:
            return (n - 1) * (n - 2) // 2 % MOD
        
        target = count // 3
        first_end = ones[target - 1]
        second_start = ones[target]
        second_end = ones[2 * target - 1]
        third_start = ones[2 * target]
        
        ways1 = second_start - first_end
        ways2 = third_start - second_end
        
        return ways1 * ways2 % MOD

public class Solution {
    public int NumWays(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        var ones = new List<int>();
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                ones.Add(i);
            }
        }
        
        int count = ones.Count;
        
        if (count % 3 != 0) {
            return 0;
        }
        
        if (count == 0) {
            return (int)((long)(n - 1) * (n - 2) / 2 % MOD);
        }
        
        int target = count / 3;
        int firstEnd = ones[target - 1];
        int secondStart = ones[target];
        int secondEnd = ones[2 * target - 1];
        int thirdStart = ones[2 * target];
        
        long ways1 = secondStart - firstEnd;
        long ways2 = thirdStart - secondEnd;
        
        return (int)(ways1 * ways2 % MOD);
    }
}

var numWays = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const ones = [];
    
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(k)

其中 n 是字符串长度，k 是字符串中'1’的个数。时间复杂度为O(n)，因为需要遍历一次字符串找到所有'1’的位置。空间复杂度为O(k)，用于存储'1’的位置。

相关题目