Edit Distance - Dynamic Programming - Leetcode 72 - Python

Thanks so much for your videos

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<int> prev(sizes+1);
vector<int> cur(sizes+1);
for(int i=0; i<sizes+1; i++){
prev[i] = sizes-i;
}
for(int i=word1.size()-1; 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?

Thanks! what do ou use the explain and draw on the screen?

Hi NeetCode. What is your rank on leetcode?

Hey NeetCode, your code is the best. Your code always helps me understand how you solved the problem.

Thanks!

Wouldn't have guessed this was LCS until you mentioned 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 .

now 72 is a medium problem not a hard

For anyone who is interested in the DFS memorization solution(C++) :

int dfs(int i, int j, string word1, string word2, unordered_map<Position, int, hashFunction>& cache) {
if(cache.count({i, j})) {
return cache[{i, j}];
}

if (i == word1.size() && j == word2.size()) {
return 0;
}

if (i == word1.size()) {
return word2.size() - j;
}

if (j == word2.size()) {
return word1.size() - i;
}

int distance = 0;
if (word1[i] == word2[j]) {
distance = dfs(i + 1, j + 1, word1, word2, cache);
} else {
// cases if we need replace, delete, insert
distance = 1 + min(dfs(i + 1, j + 1, word1, word2, cache), min(dfs(i + 1, j, word1, word2, cache), dfs(i, j + 1, word1, word2, cache)));
}

cache[{i, j}] = distance;

return distance;
}

int minDistance(string word1, string word2) {
unordered_map<Position, int, hashFunction> cache;

return dfs(0, 0, word1, word2, cache);
}

i am just so happy when i find your video

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

Can not believe that it has been downgraded to a medium question. I have completely no idea the first time saw it lol.

After watching you explanation, me be like - isn't there any hard dp problem on leetcode 🤣

You never fails at giving me an awe moment. Thank you!

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

Great explanation

holy shit, things look so simple after this video

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.

this is crazy

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

Hi sa mga kaklase ko diyan

Elegant explanation, thank you

very helpful, thanks man

Thank you so much!

This isn't optimal in terms of space.

Ok this is crazy

After listening to your solution , this problem feels more like a medium level problem. That's how good your explanation is. Thank you !

Why we need to add 1

dp = {}
def dfs(i, j):
if i == len(word1) and j == len(word2):
return 0
if i == len(word1):
return len(word2) - j
if j == len(word2):
return len(word1) - i
if (i, j) in dp:
return dp[(i, j)]
dp[(i, j)] = float("inf")
for i in range(len(word1) - 1, -1, -1):
for j in range(len(word2) - 1, -1, -1):
if word1[i] == word2[j]:
dp[(i, j)] = dfs(i + 1, j + 1)
else:
dp[(i, j)] = 1 + min(dfs(i, j + 1), dfs(i + 1, j), dfs(i + 1, j + 1))
return dp[(i, j)]
return dfs(0, 0)

I think you should draw rest of the problem.

Easy to understand explanation, clear, concise and to the point.

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.

the best explanation on the internet! thanks!

Brill. GOod job!

Best explanation for 2d dp ever!

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!

nb

thank you so much.could you help me how to use EDR on two point sets?

try this --- for j in range(len(word1) + 1, -1, -1)

Nice explanation, BTW you are Canadian lad

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

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.

Your explanations are absolutely awesome! Thanks for creating such helpful content!

Oii.Diabolical

wow, brilliant explanation. Would you like to share how to come up with this idea?

Extremely well explained! Picture perfect tutorial!

This is called Excellence