Hard

题目描述

给你一个二进制字符串 binary。binary 的一个子序列如果是 非空 的且没有 前导零（除了数字 "0" 本身），就被称为一个 好 子序列。

请你找到 binary 不同 好子序列的数目。

  • 比方说，如果 binary = "001"，那么所有的好子序列为 ["0", "0", "1"]，所以不同的好子序列为 "0" 和 "1"。 注意，子序列 "00"，"01" 和 "001" 不是好的，因为它们有前导零。

返回 binary 中不同好子序列的数目。由于答案可能很大，请将它对 10^9 + 7 取余 后返回。

子序列 指的是从原序列中删除若干个（可以是 0 个）字符后，不改变剩余字符顺序得到的序列。

示例 1：

输入：binary = "001"
输出：2
解释：好子序列为 ["0", "0", "1"]
不同的好子序列为 "0" 和 "1"

示例 2：

输入：binary = "11"
输出：2
解释：好子序列为 ["1", "1", "11"]
不同的好子序列为 "1" 和 "11"

示例 3：

输入：binary = "101"
输出：5
解释：好子序列为 ["1", "0", "1", "10", "11", "101"]
不同的好子序列为 "0", "1", "10", "11", "101"

提示：

  • 1 <= binary.length <= 10^5
  • binary 只包含 '0' 和 '1'

解题思路

这道题的关键在于理解什么是"好子序列"：非空且没有前导零的子序列（除了"0"本身）。

核心思路： 我们可以用动态规划的思想。设 ends0 表示以字符 ‘0’ 结尾的不同好子序列数目，ends1 表示以字符 ‘1’ 结尾的不同好子序列数目。

状态转移：

  • 当遇到字符 ‘0’ 时：
    • 新的以 ‘0’ 结尾的子序列数目 = 原来以 ‘1’ 结尾的子序列数目（在每个后面加 ‘0’）+ 1（单独的 “0”）
    • 以 ‘1’ 结尾的子序列数目不变
  • 当遇到字符 ‘1’ 时：
    • 新的以 ‘1’ 结尾的子序列数目 = 原来所有子序列数目的两倍（每个子序列可选择加或不加这个 ‘1’）
    • 以 ‘0’ 结尾的子序列数目不变

特殊处理： 由于题目要求没有前导零，我们需要特别处理：

  • 单独的 “0” 是合法的
  • 以 ‘0’ 开头的多位数子序列是非法的

因此，我们分别维护以 ‘0’ 和 ‘1’ 结尾的合法子序列数目，最终答案是两者之和。

代码实现

class Solution {
public:
    int numberOfUniqueGoodSubsequences(string binary) {
        const int MOD = 1e9 + 7;
        long long ends0 = 0, ends1 = 0;
        bool hasZero = false;
        
        for (char c : binary) {
            if (c == '0') {
                ends0 = ends1;
                hasZero = true;
            } else {
                ends1 = (ends0 + ends1 + 1) % MOD;
            }
        }
        
        return (ends1 + (hasZero ? 1 : 0)) % MOD;
    }
};

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        MOD = 10**9 + 7
        ends0 = ends1 = 0
        has_zero = False
        
        for c in binary:
            if c == '0':
                ends0 = ends1
                has_zero = True
            else:
                ends1 = (ends0 + ends1 + 1) % MOD
        
        return (ends1 + (1 if has_zero else 0)) % MOD

public class Solution {
    public int NumberOfUniqueGoodSubsequences(string binary) {
        const int MOD = 1000000007;
        long ends0 = 0, ends1 = 0;
        bool hasZero = false;
        
        foreach (char c in binary) {
            if (c == '0') {
                ends0 = ends1;
                hasZero = true;
            } else {
                ends1 = (ends0 + ends1 + 1) % MOD;
            }
        }
        
        return (int)((ends1 + (hasZero ? 1 : 0)) % MOD);
    }
}

/**
 * @param {string} binary
 * @return {number}
 */
var numberOfUniqueGoodSubsequences = function(binary) {
    const MOD = 1000000007;
    let endsWith0 = 0;
    let endsWith1 = 0;
    let hasZero = false;
    
    for (let char of binary) {
        if (char === '0') {
            endsWith0 = (endsWith0 + endsWith1) % MOD;
            hasZero = true;
        } else {
            endsWith1 = (endsWith0 + endsWith1 + 1) % MOD;
        }
    }
    
    return (endsWith0 + endsWith1 + (hasZero ? 1 : 0)) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目