Hey NeetCode, I really enjoy your explanations! Most channels and videos on coding do explain the algorithm before code, but they are not nearly as good, as you are with such a nuanced approach towards describing the intuition and the thought process behind the applicable algorithm. Please keep it up, this has potential to change lives!
You are amazing man and a great teacher. I had never understood the logic of the insertion and delete part of this question but you explained it very logically and beautifully. This is the best channel on UA-cam on how to approach and solve coding problems and coming out with an optimized solution. Continue the great work.
DP problems have a lot of similarity, bottom up or top down. The difficult part is more on how to derive the relation equation to connect sub-problem to main problem. More like an IQ test. Thank you Neet for another excellent explanation video. Your code is also super clean, PEP stylish!
Hands down THE BEST EXPLANATION of the solution to this question in the ENTIRE PLANET! Couldn't have explained it any better! Thank you sooo much NeetCode!
I'm studying Comp Sci online due to covid and the recorded lecture on Dynamic Programming was a bit difficult to follow. A class mate recommended your video. I checked it out and was glad I did. Liked and subcribed. Thank you so much!
oh man you made it so easy to understand this.. I spent hours watching various videos and blogs but never understood it.. i think i understand it now..
You are the best! I usually browsing news in the morning, but your tutorial uploads changed that! Love the frequency recently! Is N queens on your target list? ;-)
Insert and remove are functionally the same. If you always make word 1 longer than word 2 (by swapping if necessary), you can always use just insert or just remove
You can reduce the space complexity to O(len(word2)) or O(len(word1)) (depending on the shape of your rows) by having 2 rows in memory instead of a full grid, as you only ever need to depend on the next row.
It makes sense after seeing the solution but before that it's not so obvious that editing, replacing and inserting is just an off by one lookup in the DP table.. thanks for the vid
it's interesting that you go forward instead of backward. i always thought of going backward (from the empty strings up) -- maybe just the way the class i took was taught (i.e. you can do it by suffixes or prefixes)
nicely done i am learning through these videos cause I was not able to understand what to dointially no idea what can I do or not just doing hit and rum stuff thanks for this its help me understand what to start with and what kind of concept I would have to keep in tracjk while having something of this caliber it was quite a easy code but without this explanation of your I would never able to understand the the logic how to do .
I think a cleaner answer would be class Solution: def minDistance(self, word1: str, word2: str) -> int: n = len(word1) m = len(word2) cache = [[float("inf")] * (m+1) for i in range(n+1) ] # base case for j in range(m+1): cache[0][j] = j for i in range(n+1): cache[i][0] = i for i in range(1,n+1): for j in range(1,m+1): if word1[i-1] == word2[j-1]: cache[i][j] = cache[i-1][j-1] else: cache[i][j] = 1 + min(cache[i-1][j],cache[i][j-1],cache[i-1][j-1])#insert, delete, replace return cache[n][m]
hmm at 11:20, when you highlight cell 1,1, you're actually solving for substring "ab" for word1 & "ac" for word2. But you mention "bc" and "cd". Since this is solving for smaller problems first.
class Solution: def minDistance(self, word1: str, word2: str) -> int: M, N=len(word2), len(word1) dp = [[-1] * (M+1) for _ in range(N+1)]
for i in range(N + 1): dp[i][M] = N - i for j in range(M + 1): dp[N][j] = M - j def dfs(i, k): if dp[i][k] != -1: return dp[i][k] if word1[i]==word2[k]: dp[i][k]=dfs(i+1, k+1) else: dp[i][k]= 1 + min(dfs(i+1, k+1),#subtitution dfs(i+1, k), #delete dfs(i,k+1)) #insert return dp[i][k] return dfs(0,0) for me this was easier to understand, might help someone :)
What's the purpose for initializing every elem to inf? Aren't we filling every element right to left, bottom up anyways? We just need to make sure the edges of the matrix are filled and solve the problem in the correct order, so the value at dp[i][j] can originally be 0
We can do this in O(word2.size()) space complexity, but just using 2 arrays instead of using a 2d, we can use prev and cur array to construct the answer from bottom to up, here's the code in cpp, class Solution { public: int minDistance(string word1, string word2) { int counter = 0; int sizes = word2.size(); vector prev(sizes+1); vector cur(sizes+1); for(int i=0; i=0; i--){ counter++; cur[sizes] = counter; for(int j=sizes-1; j>=0; j--){ if(word1[i] == word2[j]){ cur[j] = prev[j+1]; } else{ int curs = min(cur[j+1], prev[j+1]); cur[j] = min(curs, prev[j]); cur[j] += 1; } } prev = cur; } return prev[0]; } };
I have noticed that the result does not change if we reverse the column and rows does that mean that converting word2 to word1 have the same distance as converting word1 to word2?
Have you ever done a “total unique combinations that add up to n” algorithm? I had that problem come up and I couldn’t write an algorithm efficient enough to pass all cases in the allotted time. It’s pretty wild, 200 ends up producing 487 million unique combinations. I know there must be a dynamic programming solution, but I couldn’t crack it.
You need a way to stop searching for more candidates when you know a path will exceed the sum. I assume the values are all positive, which means if you add an item, the sum will only increase. This means, if you sort the array, you can start with the smallest values first and subtract from the target value, if the target goes negative then you no longer need to keep on searching for candidates. Here is some python code of the solution: class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort()
def dfs(target, index, path): if target < 0: return if target == 0: res.append(path) return for i in range(index, len(candidates)): dfs(target-candidates[i], i, path+[candidates[i]])
@@tommclean9208 thanks for taking the time to think about the problem and write your solution. I agree when you say I need a way to stop calculating when the candidates reach the sum. I created several working solutions that were unfortunately not fast enough. The only thing with your solution is it’s solving a slightly different problem. In the problem I was solving, we are not given a list of candidates, only a number that all combos must add up to. In addition, we only need to return the number of combinations. So essentially, 200 goes in, 487 million is returned. It’s terribly intensive, resource wise, and I sincerely doubt there a tidy solution for this, but open to finding out! I benchmarked my best solution, it was 5 minutes to calculate 200 🙃
I'm stuck at why We cannot solve this problem with the LCS ? STEPS: 1. Find LCS of two strings. Let the length of LCS be x. 2. Let the length of the first string be m and the length of the second string be n. (m - x) will be the answer in that case.
Hi I have a question. I'm confused about why when word1[i] == word2[j] we need to use the diagonal value? How to find this pattern which is crucial to this problem. I'm new to dynamic programming. Hope someone can help. thanks in advance
question, did you come up with this solution or you've seen this problem before? i really wonder how people come up with some solution for these hard questions, I'm sure i would be just staring at the interviewer if they ask me this on an interview and i've never seen this before
I learnt that this is a well known question which is taught at the start of NLP lessons. From its number "72", can see that it is an old question and known for quite some time. But yeah, even if we know the solution, explaning the thought process in an interview is tricky.
💡 DP PLAYLIST: ua-cam.com/video/73r3KWiEvyk/v-deo.html
Your explanations are absolutely awesome! Thanks for creating such helpful content!
Hey NeetCode, I really enjoy your explanations! Most channels and videos on coding do explain the algorithm before code, but they are not nearly as good, as you are with such a nuanced approach towards describing the intuition and the thought process behind the applicable algorithm. Please keep it up, this has potential to change lives!
Oh my, this is so sweet! Great explanation, I haven’t seen a clear and concise explanation for edit distance like this.
This is the sweetest explanation of DP in general and how the bottom up approach suggests itself. Thanks a lot for this.
You are amazing man and a great teacher. I had never understood the logic of the insertion and delete part of this question but you explained it very logically and beautifully. This is the best channel on UA-cam on how to approach and solve coding problems and coming out with an optimized solution. Continue the great work.
This is crazy man, After thinking for half an hour, I had to create a whole system for this question.
You explained it so casually.
DP problems have a lot of similarity, bottom up or top down. The difficult part is more on how to derive the relation equation to connect sub-problem to main problem. More like an IQ test. Thank you Neet for another excellent explanation video. Your code is also super clean, PEP stylish!
Hands down THE BEST EXPLANATION of the solution to this question in the ENTIRE PLANET! Couldn't have explained it any better! Thank you sooo much NeetCode!
After listening to your solution , this problem feels more like a medium level problem. That's how good your explanation is. Thank you !
I have to say that again... I LOVE NEETCODE!!!!! You are the FIRST one to look for whenever I am confused about an algo question.
Amazing explanation of what the insert, delete, and replace operations mean in terms of the indexes of the words!
I don't even code in python, I learn a lot from your thinking process. big fan!!
I'm studying Comp Sci online due to covid and the recorded lecture on Dynamic Programming was a bit difficult to follow. A class mate recommended your video. I checked it out and was glad I did. Liked and subcribed. Thank you so much!
This helps me a lot, your explaination is very good. I don't think I can finish edit distance and BK-tree problem before I saw your video.
How on earth will I come up with that table logic in an interview? God bless me
Great explanation !
Finally after scratching my head for 2 days, i understand and have an intuition for the algorithm !
oh man you made it so easy to understand this.. I spent hours watching various videos and blogs but never understood it.. i think i understand it now..
Can not believe that it has been downgraded to a medium question. I have completely no idea the first time saw it lol.
Thanks for the explanation! So one of the key points is you don't need to change word1 and word2 in the function, just need to move i and j!
you really deserve being at G
G ?
@@ytg6663google
@@ytg6663gock
Google
Thank you, I spent a lot of time understanding the solution from different sources, finally understood from your video
Extremely well explained! Picture perfect tutorial!
this video is a masterpiece. the intuition flow is perfection
Wonderful explanation, but the 0 -> n approach makes for better code readability than n -> 0.
Easy to understand explanation, clear, concise and to the point.
Thank you, just realising it was changed from Hard to medium
That explanation was simply lovely!
Wouldn't have guessed this was LCS until you mentioned it!
Hey NeetCode, your code is the best. Your code always helps me understand how you solved the problem.
Hey just wanted to write that this is the best explanation of a problem solution I have ever seen. W O W
dp = [[i+j for i in range(len(word2),-1,-1)] for j in range(len(word1),-1,-1)]
this combines the first 3 loops into one
You never fails at giving me an awe moment. Thank you!
You are the best! I usually browsing news in the morning, but your tutorial uploads changed that! Love the frequency recently! Is N queens on your target list? ;-)
Thanks! Yes, I plan on doing N-Queens soon.
kudos to you man, you explained it majestically, I hope you are pursuing some teaching career cause you really are amazing
Insert and remove are functionally the same. If you always make word 1 longer than word 2 (by swapping if necessary), you can always use just insert or just remove
You can reduce the space complexity to O(len(word2)) or O(len(word1)) (depending on the shape of your rows) by having 2 rows in memory instead of a full grid, as you only ever need to depend on the next row.
Nice, you would have to just replace the old row values with the next row values one by one each time you decrement the column while traversing
That way it was explained is really impressive. Thanks a bunch!
It makes sense after seeing the solution but before that it's not so obvious that editing, replacing and inserting is just an off by one lookup in the DP table.. thanks for the vid
it's interesting that you go forward instead of backward. i always thought of going backward (from the empty strings up) -- maybe just the way the class i took was taught (i.e. you can do it by suffixes or prefixes)
Very clearly explained with code. Like it!
the best explanation on the internet! thanks!
to everyone who feels DP is tough. Keep at it. One day it will suddenly click and it will be worth it. 💪
nicely done i am learning through these videos cause I was not able to understand what to dointially no idea what can I do or not just doing hit and rum stuff thanks for this its help me understand what to start with and what kind of concept I would have to keep in tracjk while having something of this caliber it was quite a easy code but without this explanation of your I would never able to understand the the logic how to do .
Pure art! Best explanation!
i am just so happy when i find your video
Awesome explaination as always 🙏
Please add the cherry pickup problem. Your DP solutions are simple and understandable especially the bottom up approaches.
Super clear explanation! Kudos!
😯 I never would have come up with this.
Best explanation for 2d dp ever!
Amazing! Great explanations have ever seen!
I think a cleaner answer would be
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word1)
m = len(word2)
cache = [[float("inf")] * (m+1) for i in range(n+1) ]
# base case
for j in range(m+1):
cache[0][j] = j
for i in range(n+1):
cache[i][0] = i
for i in range(1,n+1):
for j in range(1,m+1):
if word1[i-1] == word2[j-1]:
cache[i][j] = cache[i-1][j-1]
else:
cache[i][j] = 1 + min(cache[i-1][j],cache[i][j-1],cache[i-1][j-1])#insert, delete, replace
return cache[n][m]
Again, thank you so much for this explanation, please keep it up!
Best explanation for edit distance
Elegant explanation, thank you
hmm at 11:20, when you highlight cell 1,1, you're actually solving for substring "ab" for word1 & "ac" for word2. But you mention "bc" and "cd". Since this is solving for smaller problems first.
Also, shouldn't initialisation happen for row = 0 & col = 0, you seem to doing it inverted. for row + 1 & col + 1. Seems counter intuitive
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
M, N=len(word2), len(word1)
dp = [[-1] * (M+1) for _ in range(N+1)]
for i in range(N + 1):
dp[i][M] = N - i
for j in range(M + 1):
dp[N][j] = M - j
def dfs(i, k):
if dp[i][k] != -1:
return dp[i][k]
if word1[i]==word2[k]:
dp[i][k]=dfs(i+1, k+1)
else:
dp[i][k]= 1 + min(dfs(i+1, k+1),#subtitution
dfs(i+1, k), #delete
dfs(i,k+1)) #insert
return dp[i][k]
return dfs(0,0)
for me this was easier to understand, might help someone :)
a big thank for you , you are doing a great job ❤❤❤
What's the purpose for initializing every elem to inf? Aren't we filling every element right to left, bottom up anyways? We just need to make sure the edges of the matrix are filled and solve the problem in the correct order, so the value at dp[i][j] can originally be 0
I love your explanation. Love u neetcode hope
Thanks!
GOD LEVEL EXPLANATION 😵
great explanation
thank you so much
Why cache[i+1, j+1] is always less or equal than (cache[i+1, j] + 1) and (cache[i, j+1] + 1) ?
I have same question 🤔
Great explanation. Is there a possibility to optimize for space
We can do this in O(word2.size()) space complexity, but just using 2 arrays instead of using a 2d, we can use prev and cur array to construct the answer from bottom to up, here's the code in cpp, class Solution {
public:
int minDistance(string word1, string word2) {
int counter = 0;
int sizes = word2.size();
vector prev(sizes+1);
vector cur(sizes+1);
for(int i=0; i=0; i--){
counter++;
cur[sizes] = counter;
for(int j=sizes-1; j>=0; j--){
if(word1[i] == word2[j]){
cur[j] = prev[j+1];
}
else{
int curs = min(cur[j+1], prev[j+1]);
cur[j] = min(curs, prev[j]);
cur[j] += 1;
}
}
prev = cur;
}
return prev[0];
}
};
I have noticed that the result does not change if we reverse the column and rows does that mean that converting word2 to word1 have the same distance as converting word1 to word2?
Thank you Neet!
Explicación perfecta!!!
Best explanation ever!
Great video, helped a lot.
Thanks! what do ou use the explain and draw on the screen?
try this --- for j in range(len(word1) + 1, -1, -1)
wow, brilliant explanation. Would you like to share how to come up with this idea?
for the else statement:cache[i + j] = 1 + min(cache[i][j + 1], cache[i+ 1][j], cache[i + 1][j +1])
why do we use 1+, where the 1 comes from? Thanks!
Best explanation as always
Thanks so much for your videos
THAT IS BRILLIANT
very helpful, thanks man
holy shit, things look so simple after this video
Excellent Content!
thank you so much.could you help me how to use EDR on two point sets?
U a DP God
great tutorial!
Have you ever done a “total unique combinations that add up to n” algorithm? I had that problem come up and I couldn’t write an algorithm efficient enough to pass all cases in the allotted time.
It’s pretty wild, 200 ends up producing 487 million unique combinations. I know there must be a dynamic programming solution, but I couldn’t crack it.
You need a way to stop searching for more candidates when you know a path will exceed the sum. I assume the values are all positive, which means if you add an item, the sum will only increase. This means, if you sort the array, you can start with the smallest values first and subtract from the target value, if the target goes negative then you no longer need to keep on searching for candidates.
Here is some python code of the solution:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
def dfs(target, index, path):
if target < 0:
return
if target == 0:
res.append(path)
return
for i in range(index, len(candidates)):
dfs(target-candidates[i], i, path+[candidates[i]])
dfs(target, 0, [])
return res
@@tommclean9208 thanks for taking the time to think about the problem and write your solution.
I agree when you say I need a way to stop calculating when the candidates reach the sum. I created several working solutions that were unfortunately not fast enough.
The only thing with your solution is it’s solving a slightly different problem. In the problem I was solving, we are not given a list of candidates, only a number that all combos must add up to.
In addition, we only need to return the number of combinations. So essentially, 200 goes in, 487 million is returned. It’s terribly intensive, resource wise, and I sincerely doubt there a tidy solution for this, but open to finding out!
I benchmarked my best solution, it was 5 minutes to calculate 200 🙃
I'm stuck at why We cannot solve this problem with the LCS ?
STEPS:
1. Find LCS of two strings. Let the length of LCS be x.
2. Let the length of the first string be m and the length of the second string be n. (m - x) will be the answer in that case.
Hi NeetCode. What is your rank on leetcode?
Thank you so much!
Nice explanation, BTW you are Canadian lad
Hi I have a question. I'm confused about why when word1[i] == word2[j] we need to use the diagonal value? How to find this pattern which is crucial to this problem. I'm new to dynamic programming. Hope someone can help. thanks in advance
Brill. GOod job!
Very helpful 👍
does the goat respond
question, did you come up with this solution or you've seen this problem before? i really wonder how people come up with some solution for these hard questions, I'm sure i would be just staring at the interviewer if they ask me this on an interview and i've never seen this before
You are just great!!!!
I think instead of using a whole new 2d cache we can use two arrays, that way my acceptance is 84% and 95% respectively.
How do they expect me to know this? Lololol
They don’t. They expect me to have it memorized from a book lolol
I learnt that this is a well known question which is taught at the start of NLP lessons. From its number "72", can see that it is an old question and known for quite some time. But yeah, even if we know the solution, explaning the thought process in an interview is tricky.
Ok this is crazy
What is the time complexity of this