leetcode_question_115 Distinct Subsequences
2104 단어 LeetCodedpdistinctsubsequence
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
. Recurse: Judge Small: Accepted! Judge Large: Time Limit Exceeded
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int slen = S.length();
int tlen = T.length();
if(slen <= tlen){
if(S == T) return 1;
else return 0;
}
if(S[slen-1] != T[tlen-1]) return numDistinct(S.substr(0,slen-1), T);
else
return numDistinct(S.substr(0,slen-1), T) + numDistinct(S.substr(0,slen-1), T.substr(0,tlen-1));
}
dp: Judge Small: Accepted! Judge Large: Accepted!
int numDistinct(string S, string T) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int col = S.length() + 1;
int row = T.length() + 1;
int** dp = new int*[row];
for(int i = 0; i < row; ++i)
dp[i] = new int[col];
for(int i = 0; i < row; ++i)
dp[i][0] = 0;
for(int j = 0; j < col; ++j)
dp[0][j] = 1;
for(int i = 1; i < row; ++i)
for(int j = 1; j < col; ++j)
if(T[i-1] == S[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = dp[i][j-1];
int tmp = dp[row-1][col-1];
for(int i = 0; i < row; ++i)
delete[] dp[i];
delete[] dp;
return tmp;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.