[leetcode] 115. Distinct Subsequences

문제 : https://leetcode.com/problems/distinct-subsequences/

---

문자열 s, t가 주어지면 t와 동일한 s의 고유한 하위 시퀀스 수를 반환하라.

답은 32비트 부호있는 정수임을 보장한다.

---

DP로 풀었다.

dp[i][j] = t[0~j]와 동일한 s[0~i]의 고유한 하위 시퀀스 수.

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i]가 t[j]인 경우)

                 dp[i][j] (s[i] 가 t[j]가 아닌 경우)

 

점화식은 위와 같다.

s[i] == t[j]인 경우 s[0~i-1] 문자열의 고유 하위 시퀀스들 문자 뒤에 s[i]를 붙이면 t[0~j]가 되므로  dp[i-1][j]에 dp[i-1][j-1]을 더해준다.

 

ex) s = "rabbbit", t = "rabbit"

1	0	0	0	0	0
1	1	0	0	0	0
1	1	1	0	0	0
1	1	2	1	0	0
1	1	3	3	0	0
1	1	3	3	3	0
1	1	3	3	3	3

정답은 32비트 부호있는 정수임을 보장하지만 중간에 나오는 횟수들은 이 범위를 넘어설 수 있으므로 32비트 정수의 최대값을 나머지 연산해서 저장해줌으로서 overflow를 방지한다.

 

시간복잡도는 O(NM) N = |s|, M = |t|.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/115.%20Distinct%20Subsequences.cpp