Check whether a string is a valid shuffle of two strings or not | Love Babbar DSA Sheet | Amazon🔥
Vložit
- čas přidán 20. 11. 2020
- #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.
String question Playlist = • Love Babbar DSA 450 Qu...
Array question Playlist = • Love Babbar DSA 450 Qu...
Love Babbar DSA Sheet : drive.google.com/file/d/1FMdN...
Hope you like it. Comment if you have any doubt
LIKE | SHARE | SUBSCRIBE
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
thanks bro ! very good explanation.
Bro great job keep continuing✌️✌️
Excellent task! Hats off😊
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.
Greatt✔✔
But i dont think this too will cover all test cases
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
Yep
behtareeen !!!
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.
Exactly. The solution, he explained is wrong. It won't cover all the test cases.
Great content
thank you bhaiya :)
Thanks you so much
You are doing a very good job !
Bro, Why you haven't used f for final check ?
why and how is it diffrent from interleaving problem please reply
Buggy code a1 and a2 and resultant string is a2a1.i points to string a1 and j to a2
well explained,thanks!
Can somone please explain how the 'f ' variable was helpful in the code??
its not required
@@rohitborra2507 Thanks
bro ye code sirf distinct characters par kaam krega agr A ya B me elements repeat hogye toh fail ho jayega
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.
If s1 = "ab", s2 = "abb" and res="abbab"....
This logic fails...
watch 1:20 ,the condition is that we cannot shuffel the order .
bro this is not suffel in correct order. "bb" will come always after a
you are right in coding ninja plt this logic is not enough
Nice
But what is the use of f
thanks..int f=0; is not required
bro but where is brute and optimal.
does the order matter?
Same characters ke liye nahi chalega ye code. But explanation achi thi bhai. Thanks
above solution is failed for the given string a = aabd , b = abdc , c= aabdabcd output is No but correct is "Yes"
aab axy aaxaby for this tet case ur code gives wrong ans
Hey bro I don't think it will work for every testcase
for ex str1="AAAAABAA" .,str2="AAAB" str3="AAABAAAAABAA"
compiler ko chkkar aagye bhai🥲🥲
good point
Then y did you taken f
Wrong Logic Fails for Test:
ab12 and abb34 are two strings, then abbab1234
This logic is for two distinct strings.
Use DP.
try this it's my logic:
#include
using namespace std;
#include
bool help(string s1, string s2, string s){
int i=s1.length();
int j=s2.length();
int k=s.length();
if(i+j!=k)
return false;
i=0;
j=0;
k=0;
while(k>s2>>s;
cout
Then how did you sove it, plz give ur code
code will fail for test case : "s1 : aabd, s2 : abdc, res : aabdabcd"
this is interleaved strings problem which can be solved using dp
Time Complexity O(n)?
Yes
O(s1.sizeof() +s2.sizeof())
It's not run for all the test cases
That's not the complete code , it won't outputs correct answer for unsorted string .
bro matrix ke bhi video banao aur array ke pending videos
First I was trying to solve important questions then after that I will be posting remaining questions 😀
@@CodeLibrary okay bro !!!
i think you forgot to mention that this method does not work for strings with duplicate characters. and f variable is useless.
can anyone send right solution ??
Pehle sort karna padenga sab strings ko tabhi chalenga ye approach..
the solution is wrong for s1 = "aabd" s2 = "abdc" and res = "aabdabcd"
bhaiya yahna pe f variable ka koi need hi nahi hai na?
There is use
@@RohitKumar-ji3vj can you explain how?
There is no need at all.but it only indicate we not Chech for all character .
source code
using dynamic + memoization
bool f(string &a,string &b,string &c,int i,int j,int k,vector&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
aab axy aaxaby bhai iss condition mai code error dega
This code will work for distinct characters....... If repeating characters are allowed then we have to check all possibilities and we have to use DP.....one question is their in DP section of sheet ...when I will solve dp section then I will explain that
why f variable
wrong solution use dp
Sorry to say but your solution is wrong as you are neglecting the case when s1[i]== s2[j] and you are prioritising s1 there. Take two strings as "demno" , "abdefmn" and resulting string as "abdedfemnmon". You cannot get the correct output if you are prioritising one string over other. Try string1 as "demno" or string2 as "demno" both ways you will fail but this testcase is a valid shuffle. Please change your solution.
Right. Sorting is required of the 3 strings before comparing.
wrong explanation in this question order does not matter of s1 and s2 in s3.
f ka zrurat nhi tha !
Question hi change krdia... Babbar dsa sheet m ye thodi hai 🙄😶
Are bhai tujhe train pakadni hoti h kya... Aaram se bta diya kr thoda