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:

1. Insert a character
2. Delete a character
3. Replace a character

Solution: DP

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        rows = len(word1) + 1
        cols = len(word2) + 1

        # dp[i][j]: edit distance between word1[:i] and word2[:j]
        dp = [[0] * cols for _ in xrange(rows)]
        for row in xrange(rows):
            dp[row][0] = row
        for col in xrange(cols):
            dp[0][col] = col

        for row in xrange(1, rows):
            for col in xrange(1, cols):
                if word1[row - 1] == word2[col - 1]:
                    dp[row][col] = dp[row - 1][col - 1]
                else:
                    dp[row][col] = min(
                        dp[row - 1][col - 1] + 1,
                        dp[row - 1][col] + 1,
                        dp[row][col - 1] + 1
                    )
        return dp[-1][-1]

Related:

• 161. One Edit Distance