72.md

72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

my thoughts:

1. typical dp. 1d dp should work and if we set rows <= cols should help the performance.

my solution:

**********412 ms
class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """        
        l1 = len(word1)
        l2 = len(word2)
        if not word1:
            return l2
        if not word2:
            return l1
        
        dp = [[0]*(l1+1) for i in range(l2+1)]
        for i in range(1, l1+1):
            dp[0][i] = i
        for i in range(1, l2+1):
            dp[i][0] = i
            
        for i in range(1, l2+1):
            for j in range(1, l1+1):
                if word1[j-1] == word2[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
        
        return dp[-1][-1]
		
**********347 ms
class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """        
        l1 = len(word1)
        l2 = len(word2)
        if not word1:
            return l2
        if not word2:
            return l1
        if l1 > l2:
            word1, word2 = word2, word1
            l1, l2 = l2, l1
        
        dp = [i for i in range(l2+1)]
            
        for i in range(1, l1+1):
            cur_dp = []
            cur_dp.append( dp[0] + 1 )
            for j in range(1, l2+1):
                if word1[i-1] == word2[j-1]:
                    cur_dp.append(dp[j-1])
                else:
                    temp = 1 + min(dp[j], dp[j-1], cur_dp[-1])
                    cur_dp.append(temp)
            dp = cur_dp
        
        return dp[-1]

my comments:

from other ppl's solution:

1. maybe this is 0d dp, 172ms:
class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        visited = {}
        queue = [(0,0)] # i,j, both exclusive
        level = 0 # number of operations
        # tuple i,j
        visited[(0,0)] = level
        while queue:
            nextQueue = []
            while queue: # use as a stack
                i,j = queue.pop()
                if i == len(word1) and j == len(word2):
                    return visited[(i,j)]
                else:
                    # try three operation
                    if i == len(word1):
                        if (i,j+1) not in visited:
                            visited[(i,j+1)] = level+1
                            nextQueue.append((i,j+1)) # insert
                    elif j == len(word2):
                        if (i+1,j) not in visited:
                            visited[(i+1,j)] = level+1
                            nextQueue.append((i+1,j))
                    else:
                        # both in range
                        if word1[i] == word2[j]:
                            if (i+1,j+1) not in visited or visited[(i+1,j+1)] == level+1:
                                visited[(i+1,j+1)] = level
                                queue.append((i+1,j+1))
                        elif (i+1,j+1) not in visited:
                            visited[(i+1,j+1)] = level+1
                            nextQueue.append((i+1,j+1))
                        if (i+1,j) not in visited:
                            visited[(i+1,j)] = level+1
                            nextQueue.append((i+1,j))
                        if (i, j+1) not in visited:
                            visited[(i+1,j)] = level+1
                            nextQueue.append((i,j+1))
            level += 1
            queue = nextQueue