leetcode 696. Count Binary Substrings （python）-一一网

【摘要】描述
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped conse…

描述

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.	

  
 
  1
  2
  3
  4
  5
  6
  7

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

  
 
  1
  2
  3

Note:

s.length will be between 1 and 50,000.
s will only consist of "0" or "1" characters.

  
 
  1
  2

解析

根据题意，就是找出所有由 0 或者 1 组成的所有合乎题意的子字符串的个数。思路简单就是找出所有 0 和 1 可能组成的合乎题意的子字符串，然后在字符串 s 中查找出现个数，最后相加即可。但是超时。

解答

class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ if len(s) <= 1: return 0 def make(n): if n % 2 != 0: n -= 1 a = '01' b = '10' r = [a, b] for i in range(n // 2 - 1): a = '0' + a + '1' b = '1' + b + '0' r.append(a) r.append(b) return r subs = make(len(s)) r = 0 for sub in subs: tmp = s.count(sub) r += tmp return r

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27

运行结果

Time Limit Exceeded

  
 
  1

解析

参考其他题又，还有一种其他解法比较巧妙，如下对 “0111001” 字符串的连续相连的 0 或 1 的记录下来，为 [1, 3, 2, 1]，然后取相邻的两个数字的较小的数字为结果追加到结果列表中，得到 [1, 2, 1] ，此列表的所有元素和即位最后结果。示意图如下。

 0 1 1 1 0 0 1 ｜ \  /  \/  ｜ [1,  3,   2,  1] \/   \/  \/ 1 + 2 + 1  = 4

  
 
  1
  2
  3
  4
  5

解答

class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ if len(s) <= 1: return 0 groups = [1] for i in range(1, len(s)): if s[i] == s[i-1]: groups[-1] += 1 else: groups.append(1) r = 0 for i in range(1, len(groups)): r += min(groups[i-1], groups[i]) return r

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

运行结果

Runtime: 200 ms, faster than 17.40% of Python online submissions for Count Binary Substrings.
Memory Usage: 15.5 MB, less than 50.95% of Python online submissions for Count Binary Substrings.

  
 
  1
  2