题目描述
给定一个字符串 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