Microsoft Coding Interview Question | Leetcode 72 | Edit Distance

In this video, we introduce how to solve the "Edit Distance" question which is used by big tech companies like Google, Facebook, Amazon in coding interviews. We also cover how to behave during a coding interview, e.g. communication, testing, coding style, etc.

Please subscribe to this channel if you like this video. I will keep updating this channel with videos covering different topics in interviews from big tech companies.

[himanshuchhikara]

In interview we have to start with recursion or can we start directly with tabulation in problem like this. or it doesn't matter much ...

[angelsancheese]

# Python version of your code
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
len_w1 = len(word1)
len_w2 = len(word2)
if len_w1 == 0 or len_w2 == 0:
return max(len_w1, len_w2)
dp = [[0 for _ in range(len_w2 + 1)] for _ in range(len_w1 + 1)]

for i in range(len_w1 + 1):
dp[i][0] = i
for i in range(len_w2 + 1):
dp[0][i] = i

i = 1
while i <= len_w1:
j = 1
while j <= len_w2:
if word1[i-1] == word2[j-1]:
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]) + 1)
else:
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
j = j + 1
i = i + 1
return dp[len_w1][len_w2]