C++LeetCode 구현(115.서로 다른 하위 시퀀스)

[LeetCode]115.Distinct Subsequences 다른 하위 시퀀스
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Example 1:
Input: S =
"rabbbit"
, T =
"rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input: S =
"babgbag"
, T =
"bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^
문자열 의 하위 시퀀스 나 배합 류 에 관 한 문 제 를 보면 먼저 동적 계획 Dynamic Programming 으로 풀 어야 합 니 다.이것 은 조건 반사 가 되 어야 합 니 다.그리고 모든 DP 문제 의 핵심 은 상태 전이 방정식 을 찾 는 것 이다.이 문 제 는 2 차원 dp 배열 을 전달 하 는 것 이다.그 중에서 dp[i][j]는 s 중의 범 위 는[0,i]의 하위 문자열 에서 t 중의 범 위 는[0,j]의 하위 문자열 의 하위 서열 의 개 수 를 구성 할 수 있다 는 것 을 나타 낸다.다음 에 우 리 는 제목 에서 준 예 를 통 해 이 2 차원 dp 배열 은 다음 과 같 아야 한다.
  Ø r a b b b i t
Ø 1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
우선,원래 문자열 과 하위 시퀀스 가 모두 비어 있 을 때 1 을 되 돌려 줍 니 다.빈 문자열 도 빈 문자열 의 하위 시퀀스 이기 때 문 입 니 다.원래 문자열 이 비어 있 지 않 고 하위 시퀀스 가 비어 있 으 면 1 을 되 돌려 줍 니 다.빈 문자열 도 임의의 문자열 의 하위 시퀀스 이기 때 문 입 니 다.원본 문자열 이 비어 있 고 하위 시퀀스 가 비어 있 지 않 을 때 0 을 되 돌려 줍 니 다.빈 문자열 이 아 닌 하위 시퀀스 가 비어 있 을 수 없 기 때 문 입 니 다.이 를 정리 하면 2 차원 배열 dp 의 가장자리 가 초기 화 될 수 있 습 니 다.다음은 상태 전이 방정식 을 찾 으 면 전체 dp 배열 을 업데이트 할 수 있 습 니 다.우 리 는 위의 2 차원 배열 을 관찰 한 결과 dp[i][j]로 업 데 이 트 될 때 dp[i][j]>=dp[i][j-1]이 항상 성립 되 고 더 관찰 한 결과 T[i-1]=S[j-1]일 때 dp[i][j]=dp[i][j-1]+ dp[i-1][j-1],기다 리 지 않 으 면, dp[i][j]=dp[i][j-1],그래서 종합 이상,전달 식 은:
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)
상기 분석 에 따 르 면 코드 는 다음 과 같다.

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<long>> dp(n + 1, vector<long>(m + 1));
        for (int j = 0; j <= m; ++j) dp[0][j] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = dp[i][j - 1] + (t[i - 1] == s[j - 1] ? dp[i - 1][j - 1] : 0);
            }
        }
        return dp[n][m];
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/115
참고 자료:
https://leetcode.com/problems/distinct-subsequences/
https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java
https://leetcode.com/problems/distinct-subsequences/discuss/37412/Any-better-solution-that-takes-less-than-O(n2)-space-while-in-O(n2)-time
C++구현 LeetCode(115.서로 다른 하위 시퀀스)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 서로 다른 하위 시퀀스 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!