How to count binary substrings in php

I recently brushed up on this question in order of difficulty. The codes I wrote at the beginning were all failed because of timeout. After going through Baidu and looking at other people’s ideas, I lamented how my previous logic was. Time consuming, below is my previous code and the code after ac.

Problem description:

Given a string s, count the number of non-empty (continuous) substrings with the same number of 0s and 1s, and all 0s in these substrings and all 1's are grouped together.

Repeated substrings need to be counted the number of times they appear.

Example 1:

输入: "00110011"输出: 6解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

Example 2:

输入: "10101"输出: 4解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

Timeout code (C#):

 public class Solution
        {
            public int CountBinarySubstrings(string s)
            {
                string temp;
                int count = 0;
                int length = 2;
                bool sign = false;
                while (length <= s.Length)
                {
                    for (int i = 0; i < s.Length - length + 1; i++)
                    {
                        sign = false;
                        temp = s.Substring(i, length);
                        int zeroend = temp.LastIndexOf(&#39;0&#39;);
                        int zerostart = temp.IndexOf(&#39;0&#39;);
                        int onestart = temp.IndexOf(&#39;1&#39;);
                        int oneend = temp.LastIndexOf(&#39;1&#39;);
                        if (zerostart == -1 || zeroend == -1 || oneend == -1 || onestart == -1)
                        {
                            sign = true;
                            continue;
                        }
                        for (int j = zerostart + 1; j < zeroend; j++)
                        {
                            if (temp[j] != &#39;0&#39;)
                            {
                                sign = true;
                                break;
                            }
                        }
                        for (int j = onestart + 1; j < oneend; j++)
                        {
                            if (temp[j] != &#39;1&#39;)
                            {
                                sign = true;
                                break;
                            }
                        }
                        if (!sign)
                            count++;
                    }
                  
                    length += 2;
                }
                return count;
            }

        }

The previous idea is the idea of ​​​​violent solution, starting from the character From the first bit of the string to its Length - the length of the string 1, find the start and end indexes of 0 and 1, and then use a loop to determine whether all are 0 or 1 in this interval. If so, count, and finally It is enough to return the value of count, but due to the high time complexity, timeout will occur, so change it to the following algorithm:

Code after change:

public class Solution
        {
            public int CountBinarySubstrings(string s)
            {
                int a = 1, b = 0;
                char num;
                bool sign = false;
                int count=0;
                num = s[0];
                int i = 0;
                int index = 0;
                while (i<s.Length-1)
                {
                    i++;
                    if (s[i] == num && sign == false)
                    {
                        a++;
                    } 
                    else if (s[i] == num && sign == true)
                    {
                        b++;
                    }
                    else if (s[i] != num && !sign)
                    {
                        b++;
                        index = i;
                        sign = true;
                        num = s[i];
                    }
                    else if (s[i] != num && sign)
                    {
                        if (a > b)
                            count += b;
                        else
                            count += a;
                        a = 1;
                        b = 0;
                        i = index;
                        sign = false;
                    }
                    if(i==s.Length-1)
                    {
                          if (a > b)
                            count += b;
                        else
                            count += a;
                    }
                }
                return count;
            }
        }

After change algorithm The idea is to traverse from the beginning to the end of the string and find the number of consecutive 1s or 0s (a in the algorithm). If the following number is different from the previous number, first write down the current index position and then find the following number. The number of the same number (b in the algorithm) until you encounter a number different from the current number again or until the end, then compare the sizes of a and b, count = the decimal of the two numbers, then count is what you are looking for Answer.

Recommendation: 《2021 PHP interview questions summary (collection)》《php video tutorial》

The above is the detailed content of How to count binary substrings in php. For more information, please follow other related articles on the PHP Chinese website!