Distinct Subsequences - LeetCode

Problem

1. input: 문자열 s, 문자열 t
2. output: s의 부분 문자열 중 t와 같은 부분 문자열의 수 리턴
   • 1 <= s.length, t.length <= 1000
   • s and t consist of English letters.

Idea

두 문자열을 비교하는 ‘Edit Distance’ 유형의 문제이다.

이전에 비슷한 문제를 푼적이 있는데 차이가 있다면, 해당 문제는 문자열 조작 중 한글자 제거만 가능 하다. 또한 가능한 모든 조작의 경우의 수를 구하는 것이므로 값을 계속 더하면서 테이블을 채워나가야 한다 → Sol1

Solution

1. DP(Tabulation)

   dp[i][j] → 문자열1[0:i]을 문자열2[0:j]로 변환할 수 있는 방법 수

   s[i] == t[i]

   • s의 i번째 문자 사용O
   • s의 i번째 문자 사용X

   s[i] != t[i]

   • s의 i번째 문자 사용X

   class Solution {
       fun numDistinct(s: String, t: String): Int {
           val sLen = s.length
           val tLen = t.length
           val dp = Array(sLen+1) { IntArray(tLen + 1) }
   				// Base 
           for (i in 0..sLen) {
               dp[i][0] = 1
           }
   				// s[0~i] t[0~j] 비교
           for (i in 1..sLen)
               for (j in 1..tLen) {
                   if (s[i-1] == t[j-1]) {
   										// 현재 비교하는 문자가 같은 경우
   										// 해당 문자 사용 + 문자 사용X
                       dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                   } else {
                       dp[i][j] = dp[i-1][j]
                   }
               }
   
           return dp[sLen][tLen]
       }
   }
   

   시간 복잡도:

   

Point