No need of DP. Recursion without DP accepted (really)


#1

I just went top-down with no memoisation. And it is accepted.

// TOP DOWN
#include<bits/stdc++.h>
int ans;
void solve(int i, int j, string& A, string& B){

// cout<<i<<" "<<j<<endl;

if(A.size()-i==B.size()-j){
    // cout<<"HERE1"<<endl<<endl;
    if(A.substr(i,A.size()-i)==B.substr(j,B.size()-j))
    // {   cout<<"H"<<endl;
        ans++;
    // }
    
    return;
}
if(A.size()-i<B.size()-j){
    // cout<<"HERE2"<<endl<<endl;
    return;
}

for(int k=i; k<A.size(); k++){
    if(A[k]==B[j]){
        // cout<<"HERE3 "<<k<<endl;
        if(j==B.size()-1){
            ans++;
            // cout<<"H"<<endl<<endl;
            // return;
        }
        if(i+1<A.size()){
            // cout<<"K"<<endl;
            if(j+1<B.size())
                solve(k+1,j+1,A,B);
            solve(k+1,j,A,B);
        }
        // cout<<endl;
        return;
    }
}
// cout<<endl;

}
int Solution::numDistinct(string A, string B) {
ans=0;
// vector<vector<int
solve(0,0,A,B);
return ans;
}