Leetcode dp Distinct Subsequences
Distinct Subsequences
Total Accepted: 15484
Total Submissions: 62324 My Submissions
Given a string S and a string T, count the number of distinct subsequences of T in S.
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). Here is an example: S =
"rabbbit" , T = "rabbit" Return
3 . 제목: 만약 어떤 문자열str1이 다른 문자열str2에서 일부 문자를 삭제하고 다른 문자가str2에서 순서를 유지한다면
그러면str1은str2의 자열이라고 합니다.
아이디어:
Edit Distance 문제랑 비슷해요.
dp[i][j]를 설정하면str1[0...j]이str2[0...i]에 나타난 횟수를 나타낸다.
dp[i][j] = dp[i - 1][j] , if str1[j] != str2[i]
왜냐하면str1[j]!=str2[i]이므로 str2[i]만 삭제할 수 있습니다
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j], if str1[j] == str2[i]
str1[j]==str2[i]이기 때문에str2[i]를 보류하거나 삭제할 수 있습니다
실현할 때 1차원 스크롤 수 있는 그룹 dp[j]-->어느 한 차원이 i상태를 계산할 때 i-1상태만 사용하면 스크롤 수 있는 그룹
-->여기가 틀린 것 같은데, 여기서 초기화할 때 각각 dp[i][0]를 1로 설정해야 하는데, 1차원 수조만 사용하면 dp[0][0]만 1로 설정할 수 있어요.
-->그래서 2차원 그룹을 사용합니다
-->인터넷에서 누군가가 1차원 그룹을 사용해도 되는데 j가 순환할 때 뒤에서 앞으로 교체된다.
복잡도: 시간 O (n^2), 공간 O (n^2)
int numDistinct(string S, string T) {
vector<vector<int> > dp(S.size() + 1, vector<int>(T.size() + 1, 0));
for(int i = 0; i <= S.size(); ++i) dp[i][0] = 1;
for(int i = 1; i <= S.size(); ++i){
for(int j = 1; j <= T.size(); ++j){
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[S.size()][T.size()];
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
