Wrong Solution in "Editorial" Section


#1

Simply equating lengths of LCS is totally wrong.
counter ex. can be as simple as
A : “q”
B : “q”
C : “qw”

A simple O(N+M) solution is possible using 2 pointers.


#2
int lcs(string A,string B){
int n=A.length(),m=B.length();
int dp[n+1][m+1];
for(int i=0;i<n+1;i++){
    for(int j=0;j<m+1;j++){
        if(i==0 or j==0) dp[i][j]=0;
        else if(A[i-1]==B[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];

}
int Solution::isInterleave(string A, string B, string C) {
unordered_map<char,int> map1;
unordered_map<char,int> map2;
string comb = A+B;
for(int i=0;i<comb.size();i++){
map1[comb[i]]++;
}
for(int i=0;i<C.size();i++){
map2[C[i]]++;
}
for(int i=0;i<C.size();i++){
if(map1[C[i]] != map2[C[i]]) return 0;
}
int m=A.length();
int n=B.length();
int k=C.length();
int x=lcs(A,C);
int y=lcs(B,C);
if(x==m && y==n) return 1;
else return 0;
}