C++ 프로그래밍의 고유한 하위 시퀀스

문자열 S와 T가 있다고 가정합니다. T와 동일한 S의 고유한 시퀀스 수를 계산해야 합니다.

우리는 문자열의 하위 시퀀스가 나머지 문자의 상대적 위치를 방해하지 않고 문자 중 일부를 제거하여(없을 수 있음) 원래 문자열에서 형성된 새로운 문자열이라는 것을 알고 있습니다. (예:"ACE"는 "ABCDE"의 하위 시퀀스이고 "AEC"는 그렇지 않음).

입력 문자열이 "baallalloonnn" 및 "balloon"이면 36가지 다른 방법으로 선택할 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=s의 크기, m :=t의 크기. s와 t 앞에 공백을 연결하여 업데이트합니다.
(n + 1) x (m + 1) 크기의 행렬 하나 만들기
dp[0, 0] :=1로 설정한 다음 모든 행의 0번째 열에 1을 설정하고 1
범위 1에서 n까지의 i에 대해
- 범위 1에서 m까지의 j에 대해
  - s[i] =t[j]이면
    - dp[i, j] :=dp[i – 1, j – 1]
  - dp[i, j] :=dp[i, j] + dp[i – 1, j]
반환 dp[n, m]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();
      s = " " + s;
      t = " " + t;
      vector < vector <lli> > dp(n + 1, vector <lli> (m + 1));
      dp[0][0] = 1;
      for(int i = 1; i <= n; i++)dp[i][0] = 1;
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
            dp[i][j]+= dp[i - 1][j];
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

입력

"baalllloonnn"
"balloon"

C++ 프로그래밍의 고유한 하위 시퀀스

예시

입력

출력