115. Distinct Subsequences ★★★

115. Distinct Subsequences

 

이 문제는 문자열 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)