O( min(M,N) ) space solution


#1

int Solution::solve(string s, string t) {
if(s.length()>t.length())
swap(s,t);
int n=s.length();
int m=t.length();
vector prev(n+1,0),curr(n+1,0);
for(int i=m-1; i>=0; i–)
{
for(int j=n-1; j>=0; j–)
{
if(s[j]==t[i])
{
curr[j]=1+prev[j+1];
}
else
{
curr[j]=max(prev[j],curr[j+1]);
}
}
for(int j=0; j<=n; j++)
prev[j]=curr[j];
}
return prev[0];
}