[DP: LCS 최장공통수열 Longest Common Subsequence] 115. Distinct Subsequences ★★★

115. Distinct Subsequences

 

두 문자열 s, t가 주어질 때, s로부터 t를 만들 수 있는 서로 다른 subsequence의 개수를 구하세요.

• subsequence: 문자의 순서는 유지하면서, 일부 문자를 생략한 것
• 각 문자는 한 번만 사용 가능

---

📌 예시 1

Input:

s = "rabbbit",

t = "rabbit"

 

Output: 3

• s에서 'b'가 3번 등장하기 때문에, 각각을 생략하는 방식으로 3가지 방법이 존재

---

📌 예시 2

Input:

s = "babgbag",

t = "bag"

 

Output: 5

• 다양한 'b', 'a', 'g' 조합이 존재해서 총 5가지 방법으로 만들 수 있음

---

🔧 핵심 개념: dp[i][j]의 의미

표현	의미
dp[i][j]	s[0:i]로 t[0:j]를 만들 수 있는 subsequence의 개수

즉, s의 앞 i글자를 사용해서 t의 앞 j글자를 만드는 경우의 수를 누적해서 저장하는 DP 테이블입니다.

---

🔄 점화식 (Recurrence)

✅ 1. 문자가 일치할 때: s[i-1] == t[j-1]

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

• dp[i-1][j-1]: 현재 문자를 사용해서 t[j-1]을 만듦
• dp[i-1][j]: 현재 문자를 건너뛰고, 이전 s로 t[0:j]을 만들던 경우 그대로 유지

✅ 2. 문자가 다를 때: s[i-1] != t[j-1]

dp[i][j] = dp[i-1][j]

• 현재 문자는 t에 사용할 수 없으므로, 무시하고 이전 s로 만들던 경우만 유지

---

🔹 초깃값 (Initialization)

• dp[i][0] = 1: 어떤 s든, 빈 문자열 t는 항상 1가지 방법으로 만들 수 있음 (아무 문자도 고르지 않음)
• dp[0][j] = 0: 빈 s로는 어떤 t도 만들 수 없음 → 0가지

---

✅ 전체 코드 + 상세 주석

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        M, N = len(s), len(t)

        # dp[i][j] = s[0:i]로 t[0:j]를 만들 수 있는 subsequence 개수
        dp = [[0] * (N + 1) for _ in range(M + 1)]
		
        """
        # 초기화: t가 빈 문자열이면 어떤 s든 1가지 방법 존재 (문자 선택 안 하는 경우)
        """
        for i in range(M + 1):
            dp[i][0] = 1

        # DP 테이블 채우기
        """
        for loop 는 1부터..
        """
        for i in range(1, M + 1):       # s의 앞 i개 문자까지 사용
            for j in range(1, N + 1):   # t의 앞 j개 문자까지 만들기
                if s[i - 1] == t[j - 1]:
                    # 문자 일치할 경우:
                    # 1. 현재 문자 사용해서 매칭 (dp[i-1][j-1])
                    # 2. 현재 문자 건너뛰고 이전 결과 유지 (dp[i-1][j])
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    # 문자 불일치 → 현재 문자 못 쓰고, 이전까지 결과만 가져옴
                    dp[i][j] = dp[i - 1][j]

        # s 전체로 t 전체를 만드는 경우의 수가 정답
        return dp[M][N]

---

👀 예시 흐름 (s = "babgbag", t = "bag")

i (s)	j (t)	s[i-1]	t[j-1]	dp[i][j] 계산 방식
3	2	b	a	불일치 → dp[2][2]
4	2	g	a	불일치 → dp[3][2]
5	2	b	a	불일치 → dp[4][2]
6	2	a	a	일치 → dp[5][1] + dp[5][2]
7	3	g	g	일치 → dp[6][2] + dp[6][3]

이런 식으로 누적해서 정답이 쌓이게 됩니다.

---

🧾 시간 및 공간 복잡도

항목	복잡도
시간	O(M × N)
공간	O(M × N) → O(N)으로 최적화 가능

---

 

 

이 문제는 문자열 s에서 문자열 t를 **부분 수열(subsequence)**로 만들 수 있는 서로 다른 방법의 수를 구하는 문제입니다.

S의 부분 수열 = 문자열 T를 만드는 수 찾는 것

이를 해결하기 위해 **동적 계획법(DP)**을 사용합니다.

---

문제 이해

1. 부분 수열 (Subsequence):
   • 문자열의 일부 문자들을 선택해 순서를 유지하면서 생성된 새로운 문자열.
   • 예: s="rabbbit", t="rabbit"
     • 부분 수열로 t를 생성하는 방법:
       1. 첫 번째 r, 첫 번째 a, 첫 번째 b, 두 번째 b, 첫 번째 i, 첫 번째 t.
       2. ...
     • 총 3가지 방법.
2. 목표:
   • s에서 t를 생성하는 모든 부분 수열의 개수를 반환.

시간 및 공간 복잡도

1. 시간 복잡도:
   • O(m×n): DP 테이블 크기에 비례.
2. 공간 복잡도:
   • O(m×n): DP 테이블 사용.

예제

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        cache = {}  # 캐싱을 위한 딕셔너리 / Cache dictionary for memoization

        def dfs(i, j):
            # t의 모든 문자를 찾았으면 1을 반환
            # If all characters in t are matched, return 1
            if j == len(t):
                return 1
            # s가 끝났는데 t를 완성하지 못한 경우 0을 반환
            # If s is fully traversed but t is not matched, return 0
            if i == len(s):
                return 0
            # 캐시가 존재하면 캐시값 반환
            # If the result for (i, j) is already computed, return it
            if (i, j) in cache:
                return cache[(i, j)]

            # 두 문자가 같으면 두 가지 선택을 고려
            # If the characters match, consider two choices:
            if s[i] == t[j]:
                # (1) 매칭하여 진행 / Match and move forward
                # (2) 건너뛰고 진행 / Skip the character in s and move forward
                cache[(i, j)] = dfs(i + 1, j + 1) + dfs(i + 1, j)
            else:
                # 두 문자가 다르면 s[i]를 건너뜀
                # If the characters don't match, skip s[i]
                cache[(i, j)] = dfs(i + 1, j)

            # 결과를 캐시에 저장하고 반환
            # Save the result in the cache and return it
            return cache[(i, j)]

        # dfs 함수 시작
        # Start the recursive DFS from the beginning of both strings
        return dfs(0, 0)