696. 计数二进制子串
Tags: 字符串
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。重复出现的子串要计算它们出现的次数。
- 最开始的思路首先没有注意到可以考虑重复子串的情况，且按照最直接的思路双重循环遍历字符串寻找满足条件的子串，时间复杂度达到
，结果超出时间限制。
- 参考官方题解，思路是依次计算整个字符串中的连续字符个数，保存在数组中，之后两两元素的遍历这个新数组，每次累加的个数是min(arr[i], arr[i+1])。此时的时间复杂度是O(n)，空间复杂度也是O(n)。
ch_cnt = []
last_ch = ''
for ch in s:
if ch != last_ch:
ch_cnt.append(1)
last_ch = ch
else:
ch_cnt[-1] += 1
res = 0
for i in range(len(ch_cnt)-1):
res += min(ch_cnt[i], ch_cnt[i+1])
return res
- 注意到2中每次只需考虑邻接的两个连续字符子串的长度，因此可以省去存储整个字符串包含的连续字符子串的数组，只记录邻接的两个连续字符子串的长度进行比较计算答案，使得空间复杂度缩小至O(1)。
# 优化空间复杂度（以下代码是每遍历到一个新字符，就进行依次结果的判断）
last_cnt = 0
this_cnt = 1
last_ch = s[0]
res = 0
for i in range(1,len(s)):
ch = s[i]
if ch != last_ch:
last_ch = ch
last_cnt = this_cnt
this_cnt = 1
res += 1
else:
this_cnt += 1
if this_cnt <= last_cnt:
res += 1
return res
以上代码略显冗余，参考题解又对代码结构进一步优化：
# 每遍历完一个连续重复字符子串再进行结果的计算
i, res, last = 0, 0, 0
while i < len(s):
ch = s[i]
cnt = 0
while i < len(s) and s[i] == ch:
i += 1
cnt += 1
res += min(cnt, last)
last = cnt
return res
