Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you an example analysis of counting binary substrings in LeetCode. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Description

Https://leetcode.com/problems/count-binary-substrings/

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

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

Example 1:

Input: "00110011" Output: 6Explanation: 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: 4Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1 s and 0 s.

Note:

S.length will be between 1 and 50000.

S will only consist of "0" or "1" characters.

Analysis

Method 1: brute force algorithm, encounter ultra-long string will time out, so abandon.

Method 2: find the rules in the string

For example, '00000111', a string of consecutive'0' and continuous'1', the substring that meets the meaning of the title is min (the number of'0', the number of'1') = min (5prime3) = 3.

For example, the string of '000011100111' is divided into an interval rule according to the same consecutive characters, and four intervals are obtained: [0prime3], [4pd6], [7pc8], [9d11].

By 2. The interval is obtained, and the pairs are paired adjacent to each other, such as [0prit 3] and [4pje 6], [4pr 6] and [7je 8], and then by 1. Get the rule to find the number of substrings in the interval of the two pairs that meet the meaning of the question, and finally add them to get the final result.

Method 3: improved version of method 2.

Submissionimport java.util.ArrayList;import java.util.List;public class CountBinarySubstrings {/ / method 1: brute force algorithm, public int countBinarySubstrings (String s) {int result = 0; / / List resultList = new ArrayList (); for (int I = 0; I < s.length (); iTunes +) {int state = 1 Char tempChar = s.charAt (I); int firstCharCount = 1, secondCharCount = 0, rightPartCount = 0; for (int j = I + 1; j < s.length () If +) {if (state = = 1) {if (tempChar = = s.charAt (j)) {firstCharCount++ } else {state = 2; tempChar = s.charAt (j) }} if (state = = 2) {if (tempChar = = s.charAt (j)) {secondCharCount++ } rightPartCount++ If (rightPartCount = = firstCharCount) {if (secondCharCount = = firstCharCount) {result++ / / resultList.add (repeat (tempChar=='1'?'0':'1', firstCharCount) + / / repeat (tempChar, secondCharCount)) } break;} return result Method 2: public int countBinarySubstrings2 (String s) {List list = new ArrayList (); int result = 0, tempIndex = 0; for (int I = tempIndex + 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.