0%

leetcode每日一题-计数二进制子串

Posted on In ,

计数二进制子串

image1

方法一：分组计数

我们可以将字符串$s$按照0和1的连续段进行分组计数存入$counts$数组，例如字符串$s=”00111011”$，那么$counts$数组为${2,3,1,2}$。数组中两个相邻的数一定代表着不同的字符，那么两个相邻的数中的较小值就是这两个数代表的子字符串中相同数量0和1的非空(连续)子字符串的数量。例如数组中第一个数和第二个数分别为2和3，代表的子字符串为$00111$，那么2就是这一子字符串中符合题意的子字符串的数量。

1
class Solution {
2
    public int countBinarySubstrings(String s) {
3
        List<Integer> counts = new ArrayList<Integer>();
4
        int pos=0, n=s.length();
5
        while(pos < n){
6
            char c = s.charAt(pos);
7
            int count = 0;
8
            while(pos<n && c == s.charAt(pos)){
9
                pos++;
10
                count++;
11
            }
12
            counts.add(count);
13
        }
14
        int ans=0;
15
        for(int i=0; i<counts.size()-1; i++){
16
            ans += Math.min(counts.get(i), counts.get(i+1));
17
        }
18
        return ans;
19
    }
20
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$。

方法二：扩展中心法

受回文串启发，本题也可以用扩展中心法来做。具体就是先找到字符串中一对不同的字符，如$”01“$或者$”10”$。找到这对字符后，再向两侧扩展，并进行计数，扩展一次就说明符合题意的字符串加1。

1
class Solution {
2
    public int countBinarySubstrings(String s) {
3
        int ans = 0;
4
        for(int i=0; i<s.length()-1; i++){
5
            if(s.charAt(i) != s.charAt(i+1)){
6
                int count = 1;
7
                int left = i-1;
8
                int right = i+2;
9
                while(left >=0 && right<s.length()){
10
                    if(s.charAt(left)==s.charAt(i) && s.charAt(right)==s.charAt(i+1)){
11
                        count++;
12
                        left--;
13
                        right++;
14
                    }else{
15
                        break;
16
                    }
17
                }
18
                ans += count;
19
            }
20
        }
21
        return ans;
22
    }
23
}

复杂度分析：

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$