The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s.rabbbitrabbbitrabbbit
Example 2:
Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s.babgbagbabgbagbabgbagbabgbagbabgbag
Constraints:
1 <= s.length, t.length <= 1000s and t consist of English letters.문자열, 동적 계획법
다음은 주어진 알고리즘 문제에 대한 코드 분석 및 풀이 방법 설명입니다.
이 문제는 두 개의 문자열 s와 t가 주어졌을 때, s의 부분 수열(subsequence) 중에서 t와 정확히 일치하는 것의 개수를 찾는 문제입니다. 여기서 '부분 수열'이란 원본 문자열의 순서를 유지하면서 몇 개의 문자를 삭제하여 얻을 수 있는 문자열을 의미합니다. '서로 다른 부분 수열'이라는 조건 때문에 단순히 일치 여부만 보는 것이 아니라, 어떤 문자를 선택하여 t를 만들었는가에 따라 다른 경우로 취급해야 합니다.
s (원본 문자열)와 t (찾으려는 부분 수열).s에서 t를 만들 수 있는 서로 다른 부분 수열의 총 개수를 나타내는 정수.s와 t의 길이는 1에서 1000 사이이며, 영어 알파벳으로 구성됩니다. 결과는 32비트 부호 있는 정수 내에 들어옵니다.예시 1: s = "rabbbit", t = "rabbit"
s에서 "rabbit"을 만들 수 있는 방법은 다음과 같이 3가지입니다:
rabbbit (첫 번째 'b'를 사용)rabbbit (두 번째 'b'를 사용)rabbbit (세 번째 'b'를 사용)이 문제는 문자열 간의 관계를 탐색하고 경우의 수를 세는 문제이므로, 중복되는 부분 문제와 최적 부분 구조를 가지는 **동적 계획법(Dynamic Programming, DP)**에 적합합니다. DP를 사용하여 s의 부분 문자열과 t의 부분 문자열 사이의 일치하는 부분 수열의 개수를 저장함으로써, 최종 답을 효율적으로 계산할 수 있습니다.
우리는 2차원 DP 테이블을 사용하여 s의 첫 i개 문자(s[:i])로 t의 첫 j개 문자(t[:j])를 만들 수 있는 서로 다른 부분 수열의 개수를 저장할 것입니다.
주어진 Python 코드는 2차원 DP 테이블을 사용하여 s에서 t를 만들 수 있는 서로 다른 부분 수열의 개수를 계산합니다.
m, n = len(s), len(t): 입력 문자열 s와 t의 길이를 각각 m과 n에 저장합니다.dp = [[0] * (n+1) for i in range(m+1)]: (m+1) x (n+1) 크기의 2차원 리스트 dp를 생성하고 모든 값을 0으로 초기화합니다.dp[i][j]의 의미: s의 처음 i개 문자 (s[0...i-1])로 t의 처음 j개 문자 (t[0...j-1])를 만들 수 있는 서로 다른 부분 수열의 개수입니다.for i in range(m+1): dp[i][0] = 1:
dp[i][0]는 s의 처음 i개 문자(s[0...i-1])로 빈 문자열 t (길이 0)를 만드는 경우의 수를 의미합니다.dp 테이블의 첫 번째 열(j=0)은 모두 1로 초기화됩니다.dp[0][j] (여기서 j > 0)는 s의 처음 0개 문자 (빈 문자열)로 t의 처음 j개 문자를 만드는 경우의 수입니다. 빈 문자열로는 비어있지 않은 문자열을 만들 수 없으므로 이 값들은 0이어야 합니다. dp 테이블이 0으로 초기화되었고, i 루프가 1부터 시작하므로 dp[0][j] 값들은 자연스럽게 0을 유지하게 됩니다.두 개의 중첩된 반복문을 사용하여 dp 테이블을 채웁니다.
for i in range(1, m+1): : s의 첫 번째 문자부터 마지막 문자까지 순회합니다. s[i-1]은 현재 s에서 고려하는 문자입니다.
for j in range(1, n+1): : t의 첫 번째 문자부터 마지막 문자까지 순회합니다. t[j-1]은 현재 t에서 고려하는 문자입니다.
if s[i-1] == t[j-1]: (현재 문자가 일치하는 경우)
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]s[i-1] 문자를 사용하여 t[j-1]을 매칭시키는 방법과 s[i-1] 문자를 사용하지 않는 방법, 두 가지가 있습니다.
dp[i-1][j-1]: s[i-1]을 t[j-1]에 매칭시키는 경우입니다. 즉, s의 이전 i-1개 문자로 t의 이전 j-1개 문자를 만드는 경우의 수를 가져옵니다.dp[i-1][j]: s[i-1]을 t[j-1]에 매칭시키지 않고 (즉, s[i-1]를 건너뛰고), s의 이전 i-1개 문자로 t의 j개 문자를 만드는 경우의 수를 가져옵니다.s[i-1]까지 사용하여 t[j-1]까지 만드는 총 경우의 수가 됩니다.else: (s[i-1] != t[j-1]) (현재 문자가 일치하지 않는 경우)
dp[i][j] = dp[i-1][j]s[i-1] 문자가 t[j-1] 문자와 다르므로, s[i-1]을 t[j-1]에 사용할 수 없습니다. 따라서 s[i-1]를 버리고, s의 이전 i-1개 문자로 t의 j개 문자를 만드는 경우의 수만 고려합니다.return dp[m][n]: 모든 반복이 완료되면 dp[m][n]에는 s 전체(s[0...m-1])로 t 전체(t[0...n-1])를 만들 수 있는 서로 다른 부분 수열의 총 개수가 저장됩니다. 이 값을 반환합니다.시간 복잡도: O(m * n)
(m+1) x (n+1)이며, 각 셀을 채우는 데 상수 시간이 걸립니다.m은 문자열 s의 길이이고, n은 문자열 t의 길이입니다.m * n에 비례합니다.공간 복잡도: O(m * n)
m과 n 길이의 문자열을 저장하는 데 필요한 공간을 제외하고, (m+1) x (n+1) 크기의 2차원 DP 테이블을 저장하기 위해 O(m * n)의 공간이 필요합니다.dp[i][j]의 정의: s의 첫 i개 문자 (s[:i])로 t의 첫 j개 문자 (t[:j])를 만들 수 있는 서로 다른 부분 수열의 개수를 나타냅니다. 이 정의를 명확히 이해하는 것이 문제 해결의 첫걸음입니다.dp[i][0] = 1: 빈 문자열 t를 만드는 경우의 수는 항상 1가지라는 점을 인식하고 DP 테이블의 첫 열을 올바르게 초기화하는 것이 중요합니다. 이는 재귀의 종료 조건과 같습니다.s[i-1] == t[j-1])와 일치하지 않는 경우 (s[i-1] != t[j-1])를 구분하여 경우의 수를 올바르게 더하는 것이 핵심입니다.
dp[i-1][j-1] (현재 s 문자를 사용하는 경우)와 dp[i-1][j] (현재 s 문자를 사용하지 않는 경우)를 합하고,dp[i-1][j] (현재 s 문자를 버리는 경우)만 고려해야 합니다.class Solution:
def numDistinct(self, s: str, t: str) -> int:
m,n = len(s), len(t)
dp = [[0] * (n+1) for i in range(m+1)]
for i in range(m+1):
dp[i][0] = 1
for i in range(1,m+1):
for j in range(1,n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
return dp[m][n]