DP 30. Minimum Insertions/Deletions to Convert String A to String B
Vložit
- čas přidán 6. 09. 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3pya8CP
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the minimum insertions and deletions to convert a String A to String B. Please watch the LCS video before doing this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
Moral of the story : DP on strings = learn LCS by heart ,❤️ Kudos to your efforts
yes bro
definitely bro
specially the *tabulation* part :
exactly , foundation for all DP problems on strings
This quote needs to be printed in notes. 🙏
that feeling of self-improvement when you don't even watch the whole video, and just in between i thought of the solution and wrote it by my own. Amazingly explained striver bhaiya
us moment bro.❤❤
Us bro us 🥹
was able to solve it without watching the video , but still watched it incase I miss anything important. Thanks a lot
I saw the length of the video and got the hint to solve it with the ongoing pattern (LCS). Coded in under 3 minutes!! Thanks Striver. I think I am really building the intuition for DP problems. I have been with the series from the beginning and I can proudly say that I can solve every single problem in this series till now with ease. I prefer solving using Recursion+Memo but I am also able to write the Tabulation solution for most of the problems. Thanks a tonne brother!!
I read your comment, got motivated, paused the video and thought for a bit, and I also solved the problem all by myself without watching the complete video, now I'm also developing confidence in solving DP problems ^_^
Same in my case , i also saw the length of video then i understand it must be solved by LCS then i solved it without watching the video😃😃
btw writing till memo during interview will not work ? means test cases surely gonna fail ? @Rishabh
Solved this after watching 1:49 minutes. There is no better person for DSA than Striver. Huge respect to you 💯
Woah! LCS proved to be a really important topic and thanks to you, I've understood it very clearly!
I Solved without watching, thank you so much striver for providing this wonderful content.
Understood, thanks for making these things like "halwa". At the same time huge respect for the amount of hardwork you must have put in to come up with these amazing (easy) logical explanations! Cheers to you buddy!
You are always providing awesome content for any level of coder noob to pro can easily understood the concept and logic.Thank you sir.
Thanks Striver. Understood.
I don't know if this intuition will occur to candidates in a real interview.
This is the first DP on strings question I did by myself ❤️ Thank you so much Striver 🙇🙏
same question @leetcode - "Delete Operation for Two Strings"
Funny story: I got this question during an interview for a startup and I had no idea it was a dp question, i just did simple hashing for both strings and compared and the interviewer said it wouldn't work but didn't seem to know in what case exactly. He couldn't prove it, so we ran it on their system and they must have had weak test cases because the code came as 100% correct and the interviewer was super impressed and told me that I had taught him a new way to solve the question and I legit got in. I didn't accept because I had one other option but still. (Hashing for this question is completely wrong btw, for anyone wondering, it ignores a very important part of the question which is the order of the letters. You can try the leetcode question and do hashing, you'll see it runs about 900 testcases and fails the rest)
shi m ye subsequence or palidrome k question m kr para hun? ......bachpan m to inke nam se hi dar lgta tha
osssm yaaar striver sir love u khud se dp solution hone lga h ab
Best Playlist on DP
Your previous video gave a thought of using the earlier concept as an application for other questions, just few changes & boom! ❤Your content is just awesome!(Topic - LCS & it's Application XD...!)😆
Hard label dekh ke hamesa fatt jati thi, now solved this problem without watching the video❤ thanks to you
You’re strong.
Thanks a lot sir! I used to dread such questions, now I am really enjoying solving 'em.
You should also put "Edit path" in title since its popular with that name. Will help in YT recommendation.
This is not Edit Distance problem but very similar to it. You can replace characters in Edit distance whereas only deletion and insertion is possible is this one.
Thanks a lot Striver, I always wondered how to solve DP questions, but now I am able to solve and think on my own!!
Without even seeing the whole video I got the logic and solved it in leetcode in one go. All thanks to striver. You are GOD of DSA.
DID THIS QUE BY MYSELF , THANK YOU STRIVER
Amazing solution...I wrote tabulated code without watching the solution...Thank you, LCS and Striver💝💝 #UNDERSTOOD
Solved even before watching this video. LCS is key ❤❤
sir !! your approches are so good and optimal
thank you sir!!
understood
typing understood has become a formality , cause we r already getting ideas to solve DP problems. Thanks striver.
Understood, Thank You so much!!
the intuition just striked by it self without watching the video
thnx striver!
Adding to this :
Delete Operation for Two Strings will also be the same solution❤.
Understood
Understood, sir. Thank you very much.
it was quite similar to the previous question, solved it in just 5min :)
First time I solved a question without looking at your approach thanks for making LCS easy
Understood Raj bro...such a easy and nice explaination
Watched every video, great series
Solved before watcing...All thanks to u bhaiya....#UNDERSTOOD!
We can do this with hashing also...
Time complexity is O(S1 length + s2 length). No recursion...
Solved it on my own
thanks to striver
#UNDERSTOOD
UNDERSTOOD... !!!
Thanks striver for the video... :)
yay! did it by myself just reading the question.
UNDERSTOOD!!!🔥🔥🔥🔥🔥🔥
"UNDERSTOOD BHAIYA!!"
Previous two questions in dp series, solved by myself . Yup 😎😎
Mind blowing before watching the video i was able to do this becuz i have watched all the previous videos and i have understood very well this is insane and thank you striver.❤❤❤❤
Al always "understood"
if we are given different costs for insertions ,deletions and replace operations.Does anyone know how to minimise the cost to convert one string to another
yeah, instead of doing "1 + helper()" in recursive relations, return "cost + helper()"
understood bhaiya
Amazing sir!!
Understood. You are awesome!!
LCS is amazing !!!
thank you bhaiya for this amaing series
Understood!!!!
Understood!!!...
Understood Completely!!!
Understood !
Understood, thank you so so much, solved it on my own completely
Understood Striver! Thank you for such fantastic explanation!
Understood ❤
understood,solved by myself.If we closely analyse the test cases we know it is n+m-2*LCS
I figured it out on my own. Your videos are awesome.
Understood 🙂🙂💚
Understood, had to take a day off yesterday because of LC contest and was a little tired of nonstop dp haha! Back on the dp so full throttle
Without watching this, I was able to solve. 🙌
Thanks sooooooooooooooooooooooooooooooo much striver. This completely amazing!!!
Understood...😊
Did this problem on myself, thanks bhaiya for making such an amazing content.
LCS is King !!
this is the 1st question I solved lcs of string
mind blowing before watching the video i was able to do this becuz i have watched all the previous videos and i have understood very well this is insane and thank you striver.
This was incredible. I don't understand the theory behind why it works( how you know this is the min there is probably a proof somewhere). But I guess you don't need too for some probrlems.
understood sir
Amazing 🤩😄 . Indescribable 💯💯🚀
Thank You
Understood!!!
solved without watching video, Thank You so much Striver bhaiya
Understood 💯💯💯
UNDERSTOOD
US You r teaching is OP
great playlist
Can anyone tell me what should we do if the question ask for "REPLACE" , "DELETE" and "INSERT"??
There is nothing to replace actually here because if it exists in both the strings then it will be considered in the longest common subsequence.
Understood :)
"THANKS BRO FOR KEEPING IT SHORT"
Understood...Completed 30/56
Understood kaka!
str.size()+ptr.size()-2*lcs(str,ptr)
understood bro, I didn't even realise that so many questions could be solved by just knowing LCS .
UNDERSTOOD ...
Solved it just by listening to question OP Striver ❤
Understood. Thankyou Sir
Amazing Series Bhaiya Loving it :))))))))
Understood SIr
Understoood
understood❤❤
understood:)😀😀
Understood!! awesome explanations!!
Understood Thank You Striver 😇
I love you man for making dp so easy 😂
Understood.
at 2:00 i was able to create logic that answer would be just no of character except the number of character in lcs
"US"