leetcode 696. Count Binary Substrings 计数二进制子串(简单)

一、题目大意

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

思路1:从左往右遍历数组，记录和当前位置数字相同中且连续的长度，以及其之前连续的不同数字的长度。举例来说，对于00110的最后一位，我们记录的相同数字长度是1，因为只有一个连续0；我们记录的不同数字长度是2，因为在0之前有两个连续的1。若不同数字的连续长度大于等于当前数字的连续长度，则说明存在一个且只存在一个当前数字结尾的满足条件的子字符串。

思路2:还可以从字符串的每个位置开始，向左向右延长，判断存在多少当前位置为中轴的由01连续二进制字符串。

三、解题方法

3.1 Java实现

public class Solution {
    public int countBinarySubstrings(String s) {
        // 输入：s = "00110011"
        // 输出：6
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            ans += extendSubstrings(s, i, i + 1);
        }
        return ans;
    }

    private int extendSubstrings(String s, int l, int r) {
        char lc = s.charAt(l);
        char rc = s.charAt(r);
        if (!((lc == '1' && rc == '0') || (lc == '0' && rc == '1'))) {
            return 0;
        }
        int count = 0;
        while (l >= 0 && r < s.length() && lc == s.charAt(l) && rc == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
        return count;
    }
}

四、总结小记

• 2202/8/28 忽如一夜秋风至，吹落黄花满地金