72. Edit Distance

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        l1=len(word1)
        l2=len(word2)
        d=[[0 for i in range(l2+1)]for j in range(l1+1)]
        for i in range(l1+1):
            d[i][0]=i
        for j in range(l2+1):
            d[0][j]=j
        for i in range(1,l1+1):
            for j in range(1,l2+1):
                if word1[i-1]==word2[j-1]:
                    d[i][j]=d[i-1][j-1]
                else:
                    d[i][j]=min(d[i-1][j-1],min(d[i-1][j],d[i][j-1]))+1
        return d[l1][l2]