```
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]
```