My simple well documented python Edit distance solution


  • 0
    S
    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]

Log in to reply
 

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