leetcode-分割字符串的方案数

66 阅读 0 评论 44 点赞

我是靠谱客的博主执着金针菇，最近开发中收集的这篇文章主要介绍leetcode-分割字符串的方案数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题外话：说实话如果面试过程中遇到这个题我绝对解不出来，但是通过做这个题感觉找回了之前做比赛的感觉了，就是可以静下心去解这道题，如果面试中出现没见过的题我想大部人是解答不出来的吧。所以个人感觉面试中的算法题很大部分看运气的。

题解

一看到这道题的s1 + s2 + s3 = s的时候，我以为是二进制的和相加是总的二进制数，然后看了事例原来只是拼接起来。要求三部分的1的个数相同，那么可以想到他们的和是相等的。我们通过前缀和来表示的应该有如下公式：

sum[j] = sum[i] - sum[j] = sum[len] - sum[i]

当遍历到i位置的时候，其实可以确定sum[len]-sum[i]的值了，也就可以确定sum[i]的值了，根据sum[j] = sum[i] - sum[j] => sum[j] * 2 = sum[i]。最终其实想要确定的是j的位置在哪里，根据公式的话就是要判断有多少个sum[j]=sum[i]/2。那么在遍历i的时候顺便保存一下sum[i]出现次数就可以了。

需要注意，因为一定要分成三份，所以最后一个数不能参数i的遍历。

例如：

1 0 0 1 0 1 0 1 j. i. len

class Solution {
public:
    int numWays(string s) {
        int mod = 1000000007;
        int sum[100005];
        int mp[100005];
        int num[100005];
        int len = s.size();
        num[0] = 0;
        memset(mp,0,sizeof(mp));
        for(int i = 0;i<len;i++) {
            if(s[i] == '0') num[i+1] = 0;
            else num[i+1] = 1;
        }

        for(int i = 1;i<=len;i++) {
            sum[i] = num[i] + sum[i-1];
        }

        int ant = 0;
        for(int i = 1;i<len;i++) {
            int x = sum[len] - sum[i];
            if(sum[i] == 2 * x) {
                ant = (ant%mod + mp[x]%mod) % mod;
            }
            mp[sum[i]] = (mp[sum[i]] + 1) % mod;
        }

        return ant % mod;

    }
};