Given a string
Repeated substrings must be counted for the number of times they appear.
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.
Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01", they have the same number of consecutive 1s and 0s.
- s.lengthBetween 1 and 50,000.
- sContains 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.
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