# LeetCode: 696. 计数二进制子串¶

## 1、题目描述¶

输入: "00110011"



输入: "10101"



• s.length 在1到50,000之间。
• s 只包含“0”或“1”字符。

## 2、解题思路¶

### 2.1 遍历法¶

​ 直接能想到的就是遍历法，不过因为时间超过了限制，所以要寻找其他办法

bool isSubstring(char *s) {
int current_count = 0;
int next_count = 0;

char cur = *s;
char *temp = s;
bool current_char = true;
while (*temp) {

if (current_char) {

if (*temp == cur) {
current_count++;
} else {
current_char = false;
next_count++;
if (next_count >= current_count) {
return true;
}
}
} else {
if (*temp != cur) {
next_count++;
if (next_count >= current_count) {
return true;
}
} else {
break;
}
}
temp++;
}

return current_count <= next_count;
}

int countBinarySubstrings(char *s) {
int result = 0;
char *temp = s;
while (*temp) {
result += isSubstring(temp);
temp++;
}

return result;

}


### 2.2 相邻最小值法¶

​ 实际上，如果相邻的值中，我们只取最小值，

00011

​ 重要的是理解题意！！！！

#define min(a, b) a<b?a:b;
int countBinarySubstrings(char* s) {
int prev_count = 0;
int current_count = 0;

int result = 0;

char *temp = s;
char cur_char = *temp;
while (*temp) {

if (*temp == cur_char) {
current_count++;
} else {
cur_char = *temp;
result += min(prev_count, current_count);
prev_count = current_count;
current_count = 1;
}

temp++;

}

result += min(current_count, prev_count);

return result;
}