72. Edit Distance

Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (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

Solution:

1. definition of each state
2. formulation to next state
3. initialization
4. return

All others are easy except step 2.

See code for commented logic

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        rowNum = len(word1)
        colNum = len(word2)

        # initialization
        dp = [[0] * (colNum+1) for row in range(rowNum + 1)]
        for row in range(rowNum + 1):
            dp[row][0] = row
        for col in range(colNum + 1):
            dp[0][col] = col

        # formulation to next state
        for row in range(rowNum):
            for col in range(colNum):
                # step 2

                if word1[row] == word2[col]:
                    # if this new char is the same for words, then move diagonally with 0
                    dp[row + 1][col + 1] = dp[row][col]
                else:
                    # if not the same, then it's the min of 3 directions (insert, replace, delete) + 1
                    dp[row + 1][col + 1] = min( dp[row][col], dp[row + 1][col], dp[row][col + 1]) + 1

        return dp[-1][-1]