Python3解leetcode Count Binary Substrings

问题描述：

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.

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.

思路：

由于s中只有0或1，并且要组成对必须是相邻的0和1才可以，基于这点，只考虑相邻的0、1即可

数量如何确定呢？明显有多少个1，就需要配置多少个0，故相邻01组合最终能凑成多少对，看0和1谁的个数最少即可。

代码：

 class Solution:

     def countBinarySubstrings(self, s: str) -> int:

         s = list(map(len, s.replace('', '1 0').replace('', '0 1').split()))

         return sum(min(i, j) for i, j in zip(s, s[1:]))

第一行代码，将01的字符串分组，每组仅仅包含0或仅仅包含1。同时计算每组中元素的个数

第二行代码，zip将相邻两个分组组合起来（每个分组中存储的是该分组元素个数），每个组合中较小的数字代表该组组合能够拆成的符合条件的子串个数，然后将所有组合能够拆成的子串个数相加，得到的结果即是最终所有的个数

巴特西

Python3解leetcode Count Binary Substrings

最新文章

热门文章