计数二进制子串

计数二进制子串

题目描述

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例：

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

分析

• 我们直接用 1100 做分析例子，我们可以看出其实他的结果就是 2，就只有两种结果[1100, 10]
• 所以我们循环这个字符串，记录相同的的数字 1的个数 = 2；然后以当前i做起点，往后遍历两位，要是都相同那么就是2种（此时重复的数字还是2），要是只有一位就只有1种（此时重复的数字就变成1了）

代码

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let length = s.length;
    if(length == 0) {
        return 0;
    }

    let count = 1;
    let prev = s[0];
    let currentNum = null;
    let result = 0;
    // s = "1100"
    let i = 1;
    while(i < length) {
        currentNum = s[i];
        if(currentNum == prev) { // 为了找相同的数字
            count++;  // 相同数字的个数
            i++;
            continue;
        }

        // prev = 1; count = 2

        // currentNum 已经跟prev 不一样了， 就是 0 => 1 , 1 => 0， 然后以i为起点，遍历后面count个数
        let j = i; 
        while(j < i + count && j < length) {
            // 这里表示 当前数字跟 前一个数字相同的话结果 + 1 ,即当前 prev = 1， s[j] = 0, 就是当前i为去起点，往后两位都是0的话就 + 2
            if(s[j] == !(prev * 1)) {      
                result++;
            } else {  
                // 此时不一样时，重新计算重复的个数
                count = j - i
                break;
            }
            j++;
        }

        i = i + count;
        prev = currentNum;
    }
    return result
};