Problem Link : https://www.interviewbit.com/problems/longest-common-subsequence/↵
↵
Can anyone help me out.↵
↵
why this code is giving time limit error(tle):↵
↵
↵
↵
↵
~~~~~↵
int fun(vector<vector<int> > &dp,int i,int j,string s1,string s2)↵
{↵
if(i==s1.length()|| j==s2.length()) return 0;↵
int &ans=dp[i][j];↵
if(ans!=-1) return ans;↵
ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2));↵
if(s1[i]==s2[j])↵
ans=max(ans,1+fun(dp,i+1,j+1,s1,s2));↵
return ans;↵
}↵
↵
↵
int Solution::solve(string s1, string s2) {↵
if(!s1.length() || !s2.length()) return 0;↵
int n=s1.size(),m=s2.size();↵
vector<vector<int> > dp(n,vector<int> (m,-1));↵
return fun(dp,0,0,s1,s2);↵
}↵
~~~~~↵
↵
↵
↵
and why this code get accepted:↵
↵
×↵
↵
~~~~~↵
int Solution::solve(string s1, string s2) {↵
if(!s1.length() || !s2.length()) return 0;↵
int n=s1.size(),m=s2.size(),i,j;↵
vector<vector<int> > dp(n+1,vector<int> (m+1,0));↵
for(i=1;i<=n;i++)↵
for(j=1;j<=m;j++)↵
{↵
if(s1[i-1]==s2[j-1])↵
dp[i][j]=1+dp[i-1][j-1];↵
else↵
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);↵
}↵
return dp[n][m];↵
}↵
~~~~~↵
↵
↵
↵
both solutions have time complexity O(m*n) ↵
memoization gives tle and tabulation passes the constraints why??↵
Thanks in advance.
↵
Can anyone help me out.↵
↵
why this code is giving time limit error(tle):↵
↵
↵
↵
↵
~~~~~↵
int fun(vector<vector<int> > &dp,int i,int j,string s1,string s2)↵
if(i==s1.length()|| j==s2.length()) return 0;↵
int &ans=dp[i][j];↵
if(ans!=-1) return ans;↵
ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2));↵
if(s1[i]==s2[j])↵
ans=max(ans,1+fun(dp,i+1,j+1,s1,s2));↵
return ans;↵
}↵
↵
↵
int Solution::solve(string s1, string s2) {↵
if(!s1.length() || !s2.length()) return 0;↵
int n=s1.size(),m=s2.size();↵
vector<vector<int> > dp(n,vector<int> (m,-1));↵
return fun(dp,0,0,s1,s2);↵
}↵
~~~~~↵
↵
↵
↵
and why this code get accepted:↵
↵
×↵
↵
~~~~~↵
int Solution::solve(string s1, string s2) {↵
if(!s1.length() || !s2.length()) return 0;↵
int n=s1.size(),m=s2.size(),i,j;↵
vector<vector<int> > dp(n+1,vector<int> (m+1,0));↵
for(i=1;i<=n;i++)↵
for(j=1;j<=m;j++)↵
{↵
if(s1[i-1]==s2[j-1])↵
dp[i][j]=1+dp[i-1][j-1];↵
else↵
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);↵
}↵
return dp[n][m];↵
}↵
~~~~~↵
↵
↵
↵
both solutions have time complexity O(m*n) ↵
memoization gives tle and tabulation passes the constraints why??↵
Thanks in advance.
