[LeetCode] 115. Distinct Subsequences

문제 URL : https://leetcode.com/problems/distinct-subsequences/description/

Distinct Subsequences - LeetCode

 

문제 접근법 :

s의 부분 문자열중에서 t가되는 문자열의 개수를 찾는문제입니다.

dp 문제이고 재귀함수를 이용한 메모이제이션 기법을 이용하면 어렵지 않게 풀수있습니다.

 

s를기준으로해서

s[idx1] 와 t[idx2] 를 비교하면서 나아가서 맞는개수를 찾으면됩니다.

 

소스코드 : 

 

class Solution {
public:
vector<vector<int>> dp;
int dfs(string &s,string &t,int l=0,int r=0){
    if(r>=t.size())return 1;
    if(l>=s.size())return 0;
    int &cache = dp[l][r];
    if(cache !=-1)return cache;
    cache = 0;
    if(s[l]==t[r])
       cache+=dfs(s,t,l+1,r+1);
    cache+=dfs(s,t,l+1,r);
    return cache;
}

int numDistinct(string s, string t) {
    dp = vector<vector<int>>(s.size(),vector<int>(t.size(),-1));
    return dfs(s,t);
}
};

처음에 제출했을때 왜 틀렸지? 했는데

영어가 안되서 문제를 자세히읽어보니  s의 부분문자열 이라고 되어있더군요 ㅠ.ㅠ

아 영알못 ㅠ.ㅠ 

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.