1987. Number of Unique Good Subsequences

[zeikar]

Problem link

https://leetcode.com/problems/number-of-unique-good-subsequences/

Problem Summary

배열의 subsequence에서 leading 0는 빼고 만들 수 있는 수의 개수를 구하는 문제.

Solution

DP이다.

DP[i][j] = i 인덱스에서 j 문자로 끝난 배열에서의 unique good subsequences의 개수

로 두면

DP[i][0] = DP[i - 1][0] + DP[i - 1][1]
DP[i][1] = DP[i - 1][0] + DP[i - 1][1] + 1

이다.

각각 문자를 이전의 결과 뒤에 붙인다고 생각하면 된다.
0은 leading zero 문제 때문에 여기서 더하진 않고 마지막에 0이 있는지만 체크해서 1 더하면 된다 (0 한글자인 경우는 valid 하다)

lee 형님의 솔루션도 참고 바람. 아주 친절히 설명해놓은 댓글도 있다.
https://leetcode.com/problems/number-of-unique-good-subsequences/discuss/1431819/JavaC%2B%2BPython-DP-4-lines-O(N)-Time-O(1)-Space

Source Code

class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        end0 = 0
        end1 = 0

        for i in range(len(binary)):
            if binary[i] == '0':
                end0 = (end0 + end1) % 1000000007
            else:
                end1 = (end0 + end1 + 1) % 1000000007

        if '0' in binary:
            return (end0 + end1 + 1) % 1000000007
        return (end0 + end1) % 1000000007