计数二进制子串 简单 字符串

题目描述

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

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

示例 1:

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

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

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

示例 2:

输入: "10101"
输出: 4
解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续 1 和 0。

解题思路

  1. 第一种解题思路就是循环遍历每一个子串,然后在子串中找出符合条件的子串,这种方式的时间消耗非常大,不是非常推荐。
  2. 第二种解法是只需要遍历一次字符串就能够进行整个操作,因为我们需要找连续的 1 和 0,所以其实我们只需要统计两个位置的 0 和 1 的个数,只要后一段的 0 或 1 的个数小于前一段的就能够凑成连续数量的 1 和 0.

代码

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
  let res = 0,
    cur = 1,
    pre = 0,
    len = s.length;
  for (let i = 1; i < len; i++) {
    if (s[i] === s[i - 1]) {
      cur++;
    } else {
      pre = cur;
      cur = 1;
    }
    if (pre >= cur) res++;
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Last Updated: 2/17/2019, 11:37:48 PM