# My simple well documented python Edit distance solution

• ``````class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
############################# AUTHOR: SUBHAM GAURAV     ##################################

# let E(i, j) be the min number of steps required to change X(1...i) to Y(1....j)
# where X(1...i): prefix of X of length i
#       Y(1...j): prefix of Y of length j
# so, the simple solution to this problem is
#       E(i, j) = min{
#                      E(i-1, j-1) + diff(i, j)  # represents replacement if diff = 1 or no action at all if diff = 0
#                      E(i-1, j) + 1             # represents deletion
#                      E(i, j-1) + 1             # represents insertion
#                     }
#       where diff(i, j) = 1 if x[i] != y[j]
#                        = 0 if x[i] == y[j]
#       Base conditions:
#             E(i, 0) = j because we need to make i deletions in X
#             E(0, j) = i because we need to make j insertions in X
# as simple as that :)

len1, len2 = len(word1)+1, len(word2)+1
edit = [[0 for _ in range(len2)] for _ in range(len1)]
for i in range(len1):
edit[i][0] = i
for i in range(len2):
edit[0][i] = i
for i in range(1, len1):
for j in range(1, len2):
edit[i][j] = min(edit[i-1][j-1] + (word1[i-1] != word2[j-1]), edit[i-1][j]+1, edit[i][j-1]+1)
return edit[-1][-1]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.