DP 33. Edit Distance | Recursive to 1D Array Optimised Solution 🔥
Vložit
- čas přidán 10. 03. 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3HcTJdy
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Edit Distance problem.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![The moment we stopped understanding AI [AlexNet]](/img/n.gif)
Hey Striver, I got this question in my Microsoft Internship Interview today, without your video I would never have solved this question so perfectly, the interviewer is indeed amazed by the space optimization that I did! Thank you so much!
Did you get the internship?
@@girishbhargava6367 Yeah, I got :)
@@Anonymous-uj3jx hey I would like ur linkdin ...can i have it ?
on campus or off campus
@@Anonymous-uj3jx dayum! congo man
After 33 lecs, 90% effort is for recursion 10% effort for memo,tabulation.space opti.
if u master recursion all the next 3 things are piece of cake.
true , we just need to understand the recurrance , its more about the question than dp itself
they say just trust the leap of faith and trust PMI , and recursion is done, i didn't do that. and i'm glad i did it my way!
Yes, agreed :)
I’m following the DP play list from the beginning. What an amazing way to deliver content, I’m really amazed to see clarity in the steps thought. Thank you sooo much :)
Hey Striver, I got the space optimization logic in the first time without looking at solution and wrong answer. All thanks to you man!
Thanks a lot again! I was always confused between insert and replace , this video finally cleared it all, also would like to add, the order is kinda important I think, like i variable is for the string that needs to be changed, j variable is kinda the target string but that does not change the answer as cost of insert for one string is the cost of deletion of another string so operations are equivalent. Correct me if I am wrong though.
Amazing Striver, you made me understand this question so easily !
Hey striver,
I was able to do it myself and all the credit goes to you and aditya Verma!
Thanks a lot
What was your intuition? Does it match with LCS pattern taught by Aditya Verma or you thought it from scratch like Striver?
i could solve this on my own, this feels so great, thanks for the previous videos!
Hey Striver , Man ur videos are just superbly fantastic. I knew only how to recursion + memo dp for the past 2years , But i did not know Bottom up dp. I could not clear online test rounds due to TLE. Now after watching ur videos in dp bottom up/recursion approaches . I got some hope that i can crack interviews in product based.
first it seemed extremely complicated, but towards the end as it unfolded, it was very clear.. u r an amazing teacher..
I've gotta say, your way of teaching is pretty awesome. I haven't come across any other CZcamsr breaking down tricky stuff like you do. It's obvious you've put in a ton of work to make things easy to understand 💯
Amazing solution Striver! Thank you so much for explaining it so patiently!!
What a wonderful person you are. I solved this problem without viewing the video because of your previous videos
Initially I thought I won't be able to solve this question by myself, but I spent some time on it, thought about the different possible cases, and got the solution on my own. Your videos are just amazing !!
Thank you so much for putting this much effort..I never thought i would do this type of hard quiestions on my own..
Jus Amazing....................................................
best explanation of edit distnce ever ....................
explained all cases with such elegance and clarity 🙏🙏
Amazing you made it look very simple ,also the optimisation part was great 🔥
You explain in such a way even a kid who do not know any thing related this, will understand😄.
Amazing video, definitely understood.
Method 1)-- recursion
i=str1_hourse || intention, j=str2_ros || extention ()
1.1)
13:37 insert operation
15:24 delete operation
16:41 replace operation
1.2)
min
1.3)
Base case 17:58
s1 exeusted 18:52 (min op to convert str1 to str2 (j+1))
s2 exeusted 20:56 (min op to convert str1 to str2_khali dusri (i+1))
1.4) space O(N+M)
and time complexity (exponential e^x) 22:05
Method 2)-- recursion memoisation 23:21 + tc & sc 23:30
2.1)-- to reduce oxillary stack space present in rec_memo we use tabulation
Method 2)---tabulation &
space optimisation
2.1) 26:58 to 28:35 one based indexing (slight change)
2.2) base case 29:24
2.3) I j ( bottom up= tabulation) 30:40
2.4) copy the recurrence
2.5)Code - 31:06
*2.6) space opt---33:16
2.7)concept of space optimasation 33:48
2.8)Code
Note : you cannot return cur[m] because , in the case when str1 is empty and str2 has element , only prev array stores the corresponding m value
True ... because of this only all test case was not passing in leetcode
Hello Striver. Thanks a lot for the amazing content. Solved the ques by myself just after understanding the question. Got a dopamine hit today.
literally THE BEST EXPLANATION for the problem
What a wonderful challenge! At first, I though this would be really tricky since we had to keep track of replacing but if we just move the index around and count them, it does all the work since we don't have to print anything. Really like this question! Understood as usual.
Thank you so much bhaiyya for this wonderful playlist, I have improved a lot on how to approach a problem and today I could solve this problem without even starting this video. Keep spreading the knowledge!!
Written Space Optimised Solution without Watching this Video ..... This show the level of concept your previous videos built. Thanks ✨💯
solved by myself. can't believe these used to look horrific a month ago. Thanks a ton man!
It is actually a very simple problem after you have simplified it so much !
Understood. extremely simple explanation, thankyou so much!
The key thing to understand is that we don't ACTUALLY have to insert, delete or replace.. we only have to count the operations. This kind of observation may seem dumb at first glance, but when approaching this problem (or similar problems) myself, this is the major thing that causes a mind block and keeps me from getting to the solution.
Great video!!🙏
Thanks Striver. Understood. Really enjoying the series.
super duper easy ... thankyou so much striver your teaching style is something different 😍😍😍
This man is no doubt a genius .You literally made tough topics seem so easy.
Thanks
Are u rich?
@@saunaknandi1814 Are u poor?
After so many lectures it is clear that the hardest part is to figure out the recursion. After that memoization,tabulation and space optimization is a piece of cake.
UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood , and i'll like to mention that till today i was a bit confused abt the working of 2 arrays space optimisation , but after dry run , it got absolutely clear.
thanks for this whole DP series , enjoying it too much.
you are the best teacher and the whole code i had written by myself without seeing your video
Thank you, Striver for this outstanding series on DP. I've been following every DP video of yours. One intuition that I explored for this problem before abandoning it was using the LongestCommonSubsequence logic. I wish you would've added explanation on why LCS approach wouldn't have worked well for this problem. After all , if you subtract out the LCS value , I would've thought using the remaining characters from both would've been enough to come up with answer.
Scared a lot by seeing the question that how we can solve it but after watching the video , the concept is crystal clear . Enjoyed it a lot
Hey Striver! We can actually space optimise it to 1D array. If we see carefully see that from the prev row, we only require j-1 so why not store that in temp variable. Below is my code in C++:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1=word1.size();
int n2=word2.size();
vector dp(n2+1,0);
dp[0]=0;
for(int j=1;j
Yess, my teachings 🥹
@@takeUforward yeah. Surely it's your teaching💯🔥
@@vanshsehgal9475 why this way of writing separately for all possibility is not working?
static int f(int i,int j,String stri, String str2)
if(i
@@techspecstm7032 bruh!! You mistakenly passed in replace function call in 1st param as 1-1. It should be i-1.
@@vanshsehgal9475 That was my typo mistake... It's correct in code but I am not getting the correct output. Am I correct in defining the recurrence?
UNDERSTOOD... !!!
Thanks striver for the video... :)
Love you Bro without your videos dp is like a nightmare to me . Thank you for your wonderful explaination and the for the time you spent to do this series.
you explain DP very well. Thanks fpr making this video :)
thankyou bhaiya , previously i was having a fear of DP, but after reaching at this video , i was able to do this hard question by myself.............and m so much happy ,thank you for helping🥺❤
Hey striver, U taught us in such a way that now LC hard problems seems to be easy. I could have solve last 3 questions including this one without watching the video. Thanks a lot for such a great content ❤️.
i have solved the last 6 question by myself now without watchinng the video... thts how good is his content
Very very good explanation!! UNDERSTOOD!!
Hey Striver, you are great man able to write the recursion on my own for this problem thanks to your series.
I'm so happy now, its a max level of satisfaction...!
Thanks sir for all of this
You are an absolute genius man!!
This was amazing thank you so much striver !!!! kind sir!!
Understood... really liked your sense of humour while explanation at 16:50
Thanks bhaiya!!! Understood
Understood Thank you so much.
very nicely explained!!
Thanks for great explanation Striver
Thank you
Understood!
Understood! So perfect explanation !!
Brilliant explanation!!
understood!!! i can't believe i did last 2 qs by myself 🔥
Understood. Thankyou Sir
God Level Explanation.
Understood sir,Honestly, you are the best.
Very Well Explained , I watched till 14:26 and then i solved it on leetcode.
Understood , ur explanations 🤌🤌
kudos to you man!
Understood, sir. Thank you very much.
Best playlist of DP that anywhere exists.....
Understood it very well
Hey striver,
I was able to solve this question today... all by myself and felt a relief that maybe there is a chance for me to get a decent package coming from Tier-3 college. And this is possible only and ONLY because of your lectures. I know saying thank you doesn't mean much, but Thank You! from the bottom of my heart. I am not financially independent as of today, but I promise... the day I am, you are one of the first person that is going to pop in my head and I will definitely gift you something. Thank You So MUCH!!!
your explanations are just beyond excellent ,US
Nice explanation.Understood the soln.
Understood :)
Self-done it fully, thanks.
July'30, 2023 23:42 pm
Understood,after getting Intuition that we can either replace ,delete ,insert a character to make it equal to other writing recursion was super easy.Just need to figure out base cases.
my interviews will be in 3 months i masterd top down and bottom up and thank you striver
Hey man you are amazing, Thank you for you hard work, you touched every aspect of the problem, but you didnt explain why you start from the beginning of the strings.
bhaii kya smjhata h ye banda🔥🔥🔥🔥
wish saare teachers aise hote
your explaination is amazing man🙌🙌
did complete question by own after learn about else 1st case(insert) striver supermacy thankyou striver
thank you sir. here after watching *distinct subsequences*.
and i am able to make recurrence by my self. 🌝🌝
Understood, did this myself.
Hey, striver after reading comments, some are able to solve on their own so i also gave it a try and hurrah! able to write the recursive code.
nice video bhaiya
Hey, I have solved a DP problem using 2 approaches and only 1 seems to works...not able to figure out why...any way you could help...
The way Raj teaches, I am able to feel he is crazy for DSA and coding and he is the best teacher ever!!!
That is what a true teacher needs to be.
if I may ask, what tools do you use to make your videos, ipad and ipencil?
Understood sir !🙏🙏
Understood ❤
Trust me I've just watch till 8:04 and thereafter I've solved till space optimization by my own! it's totally striver magic!! damn self confidence boost towards DP 🔥🔥
awesome explanation but one thing is that you should have also need to explain why not performing operation on 2nd string
What will be the time complexity of recursive approach?
Amazing Problem , Solved by myself own a LEETCODE Hard ❤❤ !! #UNDERSTOOOOOOOOOOOOOOOOD
I am back, gone for College Exams
excellent approach towards problem solving
Wow 182k subs getting a huge reach striver bro congrats , Happy and unsatisfied achievement 😅
understood!!
Understood!!Top notch!!
Wonderful explanation 😊😊
Started feeling confident now!!!!!!
It's impressive how you've explained this question not just for the sake of solving it, but to foster the development of problem-solving skills. I genuinely wish you achieve great heights in your life. Your efforts are truly appreciated. Today, I learned about your medical condition, and I'm amazed that despite that, you put in such dedicated efforts. Hats off to you!
Saw tusar Roy dp table understood everything in space optimization
Striver dp is best in the universe I can say no one can match this level amazing series
Dynamic Programming is like peace of cake
❤❤❤❤❤💯💯💯💯💯💯
Understood 😊