Why is my solution giving incorrect answers? Please help


#1

Code:

int fun(string T, string S){

int m = T.size();
int n = S.size();
if(m>n) return 0;
int dp[m+1][n+1];
for (int i = 1; i <= n; i++)
    dp[0][i] = 1;
for (int j = 0; j <= m; j++)
    dp[j][0] = 0;

for(int i=1;i<=m;++i){
    for(int j=1;j<=n;++j){
        if(T[i-1]!=S[j-1]){
            dp[i][j] = dp[i-1][j];
        }
        else{
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
        }
    }
}

return dp[m][n];
}


#2

It should be :
if(T[i-1]!=S[j-1]){
dp[i][j] = dp[i][j-1];
}
else{
dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
}
PS:According to function parameters ‘A’ and ‘B’, take string ‘T’ as ‘B’ and string ‘S’ as ‘A’ .


#3

Be clear T is “bigger” string and S is “smaller” string.Here “smaller” means its occurrences have to be found.
Problem 1: remove statement if(m>n) return 0; because firstly its incorrect and secondly if it was correct and performed what you intended it to do then also it is not needed and redundant.
Problem 2: in first for loop it should be dp[0][i]=0; as there is no sub sequence occurrence in an empty string.
Problem 3: in second for loop it should be dp[j][0]=1; as null string is a sub-sequence to any parent string.
This should work i checked it.