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:

  • Insert a character
  • Delete a character
  • Replace a character

解题方法

这种求minimum的问题，并且前后子问题之间有关系，可以直觉地往ＤＰ方面去想。

state

dp[i][j] 表示word[:i]和word[:j]的minimum edit distance

init status

  • dp[i][0] = i
  • dp[0][j] = j

这种情况下只有insert相应个数的字符

function

DP的关键就是找前后两种状态之间的关系，那么dp[i][j]之前的关系也是跟三种操作有关

  • word1 insert one character
    • dp[i][j] = dp[i-1][j] + 1
  • word2 delete one character(it's actually the same as insert)
    • 'dp[i][j] = dp[i][j-1] + 1'
  • replace a character +　在考虑replace的时候，因为我们是找与之前的状态的关系，所以我们只用考虑 当期新增的character的改变，而不需要考虑之前的edit
    • 所以也就有两种可能，取决于word1[i-1]是否等于word2[j-1]

Solution

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

        dp = [[sys.maxint for i in range(length2+1)] for j in range(length1+1)]
        dp[0][0] = 0

        for i in range(length1+1):
            dp[i][0] = i

        for j in range(length2+1):
            dp[0][j] = j

        for i in range(1, length1+1):
            for j in range(1, length2+1):
                a = dp[i-1][j] + 1
                b = dp[i][j-1] + 1
                if word1[i-1] == word2[j-1]:
                    c = dp[i-1][j-1]
                else:
                    c = dp[i-1][j-1] + 1
                dp[i][j] = min(a, b, c)

        return dp[length1][length2]

Reference