Leetcode 696. 计数二进制子串
题目描述
给定一个字符串 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。
普通解法
对字符串中每个位置上的字符，根据其后续字符串内容，判断能否构造出具有相同数量0和1的连续字符串
class Solution:
def countBinarySubstrings(self, s: str) -> int:
count=0
for i in range(len(s)-1):
c,flag=0,True
for j in range(i,len(s)):
if i==j:
if s[j]=='0':
c=1
else:
c=-1
continue
if s[j]!=s[j-1]:
if flag:
flag=False
else:
break
if s[j]=='0':
c+=1
else:
c-=1
if c==0:
count+=1
break
return count代码中以 c 变量进行计数，遇到 0 则加一，遇到 1 则减一。当 c 的值为 0，则表示子字符串中 0 和 1 的个数相同。根据题目要求，满足条件的子字符串中 0 和 1 需要是组合连续的，代码中以 flag 为 True 表示 0 或 1 的连续部分，以 False 表示 1 或 0 的连续部分。
因为该代码中存在两层循环，当示例输入较大时，会存在超时现象。
简洁解法
取两个变量 last 和 cur 分别记录上一个连续的 0 或 1 的个数，和当前连续的 1 或 0 的个数，若 last >=cur，则返回的计数结果 count 加一。
class Solution:
def countBinarySubstrings(self, s: str) -> int:
count,last,cur,tmp=0,0,0,s[0]
for i in s:
if i==tmp:
cur+=1
if last>=cur:
count+=1
else:
last,cur=cur,1
count,tmp=count+1,i
return count本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读