leetcode 696. Counting binary substrings (python)

leetcode 696. Counting binary substrings (python)

Given a string 

s
, Count the number of non-empty (continuous) substrings with the same number of 0 and 1, and all 0s and all 1s in these substrings are combined.

Repeated substrings must be counted for the number of times they appear.

Example 1:

Input: "00110011" Output: 6 Explanation: There are 6 substrings with the same number of consecutive 1s and 0s: "0011", "01", "1100", "10", "0011" and "01". Please note that some repeated substrings must be counted for the number of times they appear. In addition, "00110011" is not a valid substring, because all 0s (and 1s) are not combined.

Example 2:

Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01", they have the same number of consecutive 1s and 0s.

note:

  • s.length
     Between 1 and 50,000.
  • s
     Contains only "0" or "1" characters.
class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ #Using the map function to find the combined length of 0 and 1 that are cut apart L = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split(''))) #Because it is limited that only 0 and 1 can be next to each other, only adjacent ones can team up, using the zip function res = sum(min(a,b) for a,b in zip(L, L[1:])) return res

 Knowledge point 1: map() function

map() is a built-in higher-order function in Python. It receives a function f and a list, and by applying the function f to each element of the list in turn, a new list is obtained and returned.

Knowledge point 2: zip function

The prototype of the zip function is: zip([iterable, …])

The parameter iterable is an iterable object and can have multiple parameters. This function returns a list with tuples as elements, where the i-th tuple contains the i-th element of each parameter sequence. The length of the returned list is truncated to the length of the shortest parameter sequence. When there is only one sequence parameter, it returns a list of 1-tuples. When there are no parameters, it returns an empty list.

 

Method Two:

The method below is easy to understand, but it cannot be AC ​​(because the time limit is exceeded)

class Solution: def countBinarySubstrings(self, s): """ :type s: str :rtype: int         """         if(len(s)<2 or s.count('0')==len(s) or s.count('1')==len(s)): return 0 s2='01' s3='10' out=0 while(s.count(s2) or s.count(s3)): out+=s.count(s2) s2='0'+s2+'1' out+=s.count(s3) s3='1'+s3+'0' return out

Reference : https://blog.csdn.net/weixin_40449300/article/details/83477896