DP 33. Edit Distance | Recursive to 1D Array Optimised Solution 🔥
ฝัง
- เผยแพร่เมื่อ 10 ก.พ. 2025
- Lecture Notes/C++/Java Codes: takeuforward.o...
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/take...
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.o...
You can also get in touch with me at my social handles: linktr.ee/take...
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 :)
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
Thanks
Are u rich?
@@saunaknandi1814 Are u poor?
Hey striver,
I was able to do it myself and all the credit goes to you and aditya Verma!
Thanks a lot
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!
I've gotta say, your way of teaching is pretty awesome. I haven't come across any other TH-camr breaking down tricky stuff like you do. It's obvious you've put in a ton of work to make things easy to understand 💯
first it seemed extremely complicated, but towards the end as it unfolded, it was very clear.. u r an amazing teacher..
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 !!
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.
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.
Jus Amazing....................................................
best explanation of edit distnce ever ....................
explained all cases with such elegance and clarity 🙏🙏
You explain in such a way even a kid who do not know any thing related this, will understand😄.
Amazing video, definitely understood.
Written Space Optimised Solution without Watching this Video ..... This show the level of concept your previous videos built. Thanks ✨💯
What a wonderful person you are. I solved this problem without viewing the video because of your previous videos
UNDERSTOOD.........Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Today is 4th September
Tomorrow is 5th september which is teacher's day,
And I want to thank this amazing teacher of ours.
Thankyou Raj
Thankyou Striver
You're one of the best teachers I have got in my life.
Yes bro i am also following the dp series and doing codes effortlessly ❤ Happy Teachers day My Best Teacher striver Gurujii ❤❤
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 Man
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.
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
I having more confident now in dp , thank u striver bhaiya.
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 🔥🔥
Amazing Striver, you made me understand this question so easily !
This man is no doubt a genius .You literally made tough topics seem so easy.
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
i could solve this on my own, this feels so great, thanks for the previous videos!
Very Well Explained , I watched till 14:26 and then i solved it on leetcode.
solved by myself. can't believe these used to look horrific a month ago. Thanks a ton man!
i am also following the dp series and doing codes effortlessly ❤ Happy Teachers day My Best Teacher striver Gurujii ❤❤
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!
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
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.
you are the best teacher and the whole code i had written by myself without seeing your video
literally THE BEST EXPLANATION for the problem
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?
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.
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.
Understood... really liked your sense of humour while explanation at 16:50
The best thing about Striver's video is you don't need to watch the full video sometimes, as he is explaining the problem or explaining the approach to question the solution just clicks to you . Dont even need to look at the code. Best feeling ever when its a difficult topic or approach.
Bhaiya i have no words ........just a smile on my face full of gratitude !!
Thanks alot for your hard work and support
Thank you so much for putting this much effort..I never thought i would do this type of hard quiestions on my own..
super duper easy ... thankyou so much striver your teaching style is something different 😍😍😍
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.
bhaii kya smjhata h ye banda🔥🔥🔥🔥
wish saare teachers aise hote
awesome explanation but one thing is that you should have also need to explain why not performing operation on 2nd string
It is actually a very simple problem after you have simplified it so much !
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!!!
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
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.
Understood. extremely simple explanation, thankyou so much!
This was a tough question,and I have seen this lots of time in Contests
Now I understood how to solve these kind of question
THanks to you
At 24:40
Starting from C++11, you can use std::min with an initializer list like
_min({delete, replace, insert})_
you need to add algorithm header file to use that.
Hello Striver. Thanks a lot for the amazing content. Solved the ques by myself just after understanding the question. Got a dopamine hit today.
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
❤❤❤❤❤💯💯💯💯💯💯
Thanks Striver. Understood. Really enjoying the series.
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🥺❤
Understood :)
Self-done it fully, thanks.
July'30, 2023 23:42 pm
Amazing solution Striver! Thank you so much for explaining it so patiently!!
understood!!! i can't believe i did last 2 qs by myself 🔥
Amazing Problem , Solved by myself own a LEETCODE Hard ❤❤ !! #UNDERSTOOOOOOOOOOOOOOOOD
I am back, gone for College Exams
Understood sir,Honestly, you are the best.
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!!
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.
Amazing you made it look very simple ,also the optimisation part was great 🔥
God Level Explanation.
my interviews will be in 3 months i masterd top down and bottom up and thank you striver
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.
thank you sir. here after watching *distinct subsequences*.
and i am able to make recurrence by my self. 🌝🌝
Best playlist of DP that anywhere exists.....
Understood ❤
You are an absolute genius man!!
did complete question by own after learn about else 1st case(insert) striver supermacy thankyou striver
Very very good explanation!! UNDERSTOOD!!
Thanks for great explanation Striver
Thank you
Understood!
Hey @striver, you can actually space optimize it to 1 row, you just need to have a variable which will store the prev value of j-1 index
I am truly amazed by your ability to simplify such complex problems. How do you make it look so easy every time?
Can't thank you enough for this series. You're the best! 💯✨️
amazing shortcut for python users no need to do memoization manually just use lru cache decorater
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
@lru_cache(maxsize=None)
def helper(i,j,s1,s2):
if i==-1:
return j+1
if j==-1:
return i+1
if s1[i]==s2[j]:
return 0+helper(i-1,j-1,s1,s2)
insert = 1+helper(i,j-1,s1,s2)
delete = 1+helper(i-1,j,s1,s2)
replace = 1+helper(i-1,j-1,s1,s2)
return min(insert,delete,replace)
return helper(len(word1)-1,len(word2)-1,word1,word2)
you explain DP very well. Thanks fpr making this video :)
I have did it in my own!
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if word1 == "" and word2 == "":
return 0
if word1 == "":
return len(word2)
if word2 == "":
return len(word1)
def help(i, j, s, t):
if j < 0 and i < 0:
return 0
if i < 0:
return j + 1
if j < 0:
return i + 1
if s[i] == t[j]:
return help(i - 1, j - 1, s, t)
insert = help(i, j - 1, s, t) + 1
remove = help(i - 1, j, s, t) + 1
replace = help(i - 1, j - 1, s, t) + 1
return min(insert, remove, replace)
#dp = [[-1 for i in range(len(word2) + 1)] for j in range(len(word1) + 1)]
current = [-1 for i in range(len(word2) + 1)]
prev = [-1 for i in range(len(word2) + 1)]
for i in range(len(word1) + 1):
for j in range(len(word2) + 1):
if i == 0 and j == 0:
current[j] = 0
elif i == 0:
current[j] = j
elif j == 0:
current[j] = i
elif word1[i - 1] == word2[j - 1]:
current[j] = prev[j - 1]
else:
insert = current[j - 1] + 1
remove = prev[j] + 1
replace = prev[j - 1] + 1
current[j] = min(insert, remove, replace)
prev = current[:]
#print(dp)
return prev[len(word2)]
#return help(len(word1) - 1, len(word2) - 1, word1, word2)
Thank you soo much bhaiya for your incredible DP playlist! Following it from the beginning has made me clear and confident enough to solve any DP problem. Your teaching is awesome and truly made a difference!"
Undestood Understood Understood
But i have 1 question here can't we just store the previous (i-1, j-1) into some temp variable and then optimise the problem to use only 1D array .
I did the same and it worked on leetcode
class Solution {
public int minDistance(String word1, String word2) {
int WIL word1.length(), W2L word2.length(); int[] dp = new int[W2L+1];
for(int i = 0; i
This is a cream question guys. Understand it very clearly. If you understand you are probably good with DP on strings.
passing strings by referance took my program from being better than 5% solutions to being better than 60% solutions.
and i was never using this i just kept passing strings of integers without referance.
thanks!!
excellent approach towards problem solving
Best DP Series ever!!!
Understood , ur explanations 🤌🤌
How to solve this question where only shifting of one character from back to front is allowed?
The Levenshtein distance (or Edit distance) is a way of quantifying
how different two strings are from one another by counting
the minimum number of operations required to transform one string into the other.
str1 = "ADCB"
str2 = "ABCD"
ADCB -> CADB (Move ‘C’ to the front)
CADB -> BCAD (Move ‘B’ to the front)
BCAD -> ABCD (Move ‘A’ to the front)
Allowed to move one character to the front from the first string.
Saw tusar Roy dp table understood everything in space optimization
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.
IDK STRIVER IF YOU ARE READING THIS BUT I HATS OFF TO YU , I AM WATCHING DP AND AT 18.00 ;LITERALLY I CLAPPED AND SALUTED U . THIS IS HANDS DOWN THE BEST VIDEO EVER, PLEASE COME TO NORTHCAP UNIVERSITY PLEASEEEE
It was a cakeWalk bruh
I remember from hearing from piyus agarwal on one of his videos that for an candidate master an amazon interview is a piece of cake walk and I wondered but now i Can see that the most difficult problems are easy now . Thank you bhaiyaa for everything......
Started feeling confident now!!!!!!
We need video on Word Break problem.
Done and dusted in the DP revision :)
13 mins
Nov'17, 2023 07:27 pm
UNDERSTOOD... !!!
Thanks striver for the video... :)
US Best dp series🔥
striver has got so less follower ...i dont get it....he is G.O.A.T
amazing analyzation sir
bhaiya will u teach DP on graphs and Trees ? @TakeUForward