以下是 LeetCode 1987 “不同的好子序列数目” 的 Python3 实现,沿用之前分析的动态规划思路:

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        MOD = 1_000_000_007
        ends0 = 0   # 以 '0' 结尾的好子序列数
        ends1 = 0   # 以 '1' 结尾的好子序列数
        has_zero = False

        for ch in binary:
            if ch == '0':
                has_zero = True
                # 所有已有的好子序列后面追加 '0',形成新的以 '0' 结尾的子序列
                ends0 = (ends0 + ends1) % MOD
            else:  # ch == '1'
                # 所有已有的好子序列后面追加 '1',加上单独的 "1"
                ends1 = (ends0 + ends1 + 1) % MOD

        ans = (ends0 + ends1) % MOD
        if has_zero:
            ans = (ans + 1) % MOD   # 单独的 "0"
        return ans

简要说明

  • ends0:以 '0' 结尾的、满足要求的 不同 好子序列个数。
  • ends1:以 '1' 结尾的、满足要求的 不同 好子序列个数。
  • 遇到 '1' 时,将所有已有的好子序列(ends0 + ends1)后追加 '1',再加上单个 "1",得到新的 ends1
  • 遇到 '0' 时,只追加,不包含单个 "0"(否则会产生前导零问题)。
  • 最后,如果原字符串中包含 '0',则额外加上单个 "0" 这个子序列。

这样保证了所有计数均无前导零,且不重复。时间复杂度 O(n),空间复杂度 O(1)。

更多推荐