Check whether a string is a valid shuffle of two strings or not | Love Babbar DSA Sheet | Amazon🔥

#competitiveprogramming #dsasheet #interviewpreparation

In this video I have solved the problem of the sheet i.e. Check whether a string is a valid shuffle of two strings or not.
Complete Explaination with code.

Hope you like it. Comment if you have any doubt

LIKE | SHARE | SUBSCRIBE

[akshatthakur]

actually like we matched s1 first and then s2, likewise we should also look for matching s2 first then s1. If either of this satisfies both the strings then answer is true. eg. take s1 = xy, s2 = zyb and res = xzyby. if we match elements of s1 first then it would return false.

[_adityakumar]

Interleaved string on leetcode and this problem both are same.I think there is no any two pointer approach to this problem.It can be solved by only using Dynamic programming.Two pointer would not be able to handle a lot of cases.

[manavkapur]

aabcc dbbca aadbcbbcac not working for this test case!! Here for last case we will have c and ca now algo will select c first then will go for c in next string but then it will give us error

[mustafandf]

If s1 = "ab", s2 = "abb" and res="abbab"....
This logic fails...

[anshulvairagade]

Thanks you so much
You are doing a very good job !

[Ganesh-dusw]

i would like to suggest you one thing that you should have to start from worst case to best case for every solution because it will help to beginner
they will understand the meaning of optimization

[animeshjain]

Buggy code a1 and a2 and resultant string is a2a1.i points to string a1 and j to a2

[codeshahar]

Bro, Why you haven't used f for final check ?

[ROSHANKUMAR-rlbf]

why and how is it diffrent from interleaving problem please reply

[gouravmalik]

bro ye code sirf distinct characters par kaam krega agr A ya B me elements repeat hogye toh fail ho jayega

[meb]

Can somone please explain how the 'f ' variable was helpful in the code??

[roshanraut]

Wrong Logic Fails for Test:
ab12 and abb34 are two strings, then abbab1234

[igautammunot]

code will fail for test case : "s1 : aabd, s2 : abdc, res : aabdabcd"
this is interleaved strings problem which can be solved using dp

[ranjeet]

bhai thnx for such a great video. one thing that caught my attention was the flow of your speaking became so good after switching to Hinglish. Thank you.

[rohitprajapati]

above solution is failed for the given string a = aabd , b = abdc, c= aabdabcd output is No but correct is "Yes"

[rahulvig]

Same characters ke liye nahi chalega ye code. But explanation achi thi bhai. Thanks

[YashSharma-dzuu]

using dynamic + memoization

bool f(string &a, string &b, string &c, int i, int j, int k, vector<vector<int>>&dp){
if(i==a.size() && j==b.size() && k==c.size()) return true;

if(dp[i][j]!=-1) return dp[i][j];
bool ans;
if((i<a.size() && a[i]==c[k]) && (j<b.size() && b[j]==c[k])) ans= f(a, b, c, i+1, j, k+1, dp) || f(a, b, c, i, j+1, k+1, dp);
else if(i<a.size() && a[i]==c[k]) ans= f(a, b, c, i+1, j, k+1, dp);
else if(j<b.size() && b[j]==c[k]) ans= f(a, b, c, i, j+1, k+1, dp);
else ans= false;
return dp[i][j]=ans;
}
bool isInterleave(string a, string b, string c){
int l1=a.size(), l2=b.size(), l3=c.size();
vector<vector<int>>dp(l1+1, vector<int>(l2+1, -1));
if(l1+l2!=l3) return false;
return f(a, b, c, 0, 0, 0, dp);

}

[AbhishekKumar-wxrw]

the solution is wrong for s1 = "aabd" s2 = "abdc" and res = "aabdabcd"

[GauravSharma-ginc]

Hey bro I don't think it will work for every testcase
for ex ., str2="AAAB"

[vishwajeetchoudhary]

That's not the complete code, it won't outputs correct answer for unsorted string .