DeepSeek LeetCode 1987. 不同的好子序列数目 Python3实现
·
以下是 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)。
更多推荐



所有评论(0)