LeetCode每日一题(1573. Number of Ways to Split a String)

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: s = “10101”
Output: 4

Explanation: 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: 3

Explanation: There are three ways to split s in 3 parts.

“0|0|00”
“0|00|0”
“00|0|0”

Constraints:

• 3 <= s.length <= 105
• s[i] is either ‘0’ or ‘1’.

---

整体分成 3 种情况：

1. 全是 0 的情况
2. 1 的数量不能被 3 整除的情况
3. 1 的数量可以被 3 整除的情况

情况 2 很简单，直接返回 0 即可。

情况 1 我们其实相当于将放 2 个隔板到任意 2 个槽里, 我们认为两个数之间是一个槽， 比如"0000"就有 3 个槽， 当我们将第一个挡板放到 slot[i]里面的时候， 我们第二个挡板可以放置在槽的总数量-i-1个槽当中， 注意 i 从 0 开始， 所以我们只需要将这些选项数量相加即可， 时间复杂度 O(n)

情况 2 的话其实我们要找的是三组之间的 0 的数量， 比如"10100101000101", 我们可以把它拆解为 101|00|101|000|101, 每组含有 1 的组的两端一定都是 1, 也就是最小的符合题目要求的组， 这其中的 00 和 000， 与两边的 1 进行组合分别是 1001, 10001, 我们可以在其中任何一个槽上放置挡板， 所隔成的组一定是符合题目标准的， 1001 有 3 个槽， 10001 有 4 个槽， 这样我们实际的选择有 3 * 4 = 12 种

---

impl Solution {
    pub fn num_ways(s: String) -> i32 {
        let one_num = s.chars().filter(|v| v == &'1').count();
        if one_num % 3 != 0 {
            return 0;
        }
        let mut ans = 0i64;
        if one_num == 0 {
            let slot_num = s.len() - 1;
            for i in 0..slot_num {
                ans += slot_num as i64 - i as i64 - 1;
            }
            return (ans % (10i64.pow(9) + 7)) as i32;
        }
        let mut zero_span1 = 0;
        let mut zero_span2 = 0;
        let mut prev_one_index = -1;
        let mut ones = 0;

        for (i, c) in s.chars().enumerate() {
            if c == '1' {
                ones += 1;
                if ones == one_num / 3 + 1 {
                    if prev_one_index == -1 {
                        zero_span1 = i as i64 + 1;
                    } else {
                        zero_span1 = i as i64 - prev_one_index;
                    }
                } else if ones == one_num / 3 * 2 + 1 {
                    if prev_one_index == -1 {
                        zero_span2 = i as i64 + 1;
                    } else {
                        zero_span2 = i as i64 - prev_one_index;
                    }
                    break;
                }
                prev_one_index = i as i64;
            }
        }
        (zero_span1 * zero_span2 % (10i64.pow(9) + 7)) as i32
    }
}

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