分割字符串的方案数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个二进制串 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

# 思路

定义常量 MOD，用于后续结果取模

# 解法

class Solution {
    // 定义常量 MOD，用于后续结果取模
    private static final int MOD = 1_000_000_007;

    public int numWays(String s) {
        int totalOnes = 0;
        
        // 统计字符串中 '1' 的总数
        for (char c : s.toCharArray()) {
            if (c == '1') totalOnes++;
        }

        // 如果 '1' 的总数不能被 3 整除，则无法分割成三个相同数量的 '1'，直接返回 0
        if (totalOnes % 3 != 0) return 0;

        // 如果字符串中没有 '1'，即 totalOnes == 0，所有字符都是 '0'，可以通过组合数来计算分割方式
        if (totalOnes == 0) {
            int n = s.length();
            // 计算可以从 (n-1) 个位置中选择 2 个位置进行分割，即组合数 C(n-1, 2)
            return (int)((long)(n - 1) * (n - 2) / 2 % MOD);
        }

        // 每一部分的 '1' 数量
        int onesPerPart = totalOnes / 3;
        //分别表示可以进行第一次和第二次分割的方式数量。
        int firstSplitWays = 0, secondSplitWays = 0;
        int currentOnes = 0;  // 当前遍历过程中 '1' 的数量

        // 遍历字符串，计算第一次和第二次分割可能的方式数
        for (char c : s.toCharArray()) {
            if (c == '1') currentOnes++;  // 每遇到一个 '1'，就增加 currentOnes 的计数

            // 如果 currentOnes 达到了每个部分应该包含的 '1' 数量，则可能成为第一次分割点
            if (currentOnes == onesPerPart) firstSplitWays++;

            // 如果 currentOnes 达到了两倍的 onesPerPart，则可能成为第二次分割点
            if (currentOnes == 2 * onesPerPart) secondSplitWays++;
        }
        //最终的分割方案数是第一次分割方式数 firstSplitWays 与第二次分割方式数 secondSplitWays 的乘积
        //乘法可能会造成溢出  结果对 MOD 取模
        return (int)((long)firstSplitWays * secondSplitWays % MOD);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 总结

分析出几种情况，然后分别对各个情况实现

#Java