sighhhhh,the question seems so clearly. why is so difficult to write down the correct answer.

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

it’s obvious that f(n) bases on f(n-1)

also we have three options.insert,delete or replace.

so the minimum is among these three .

======>

f(n) = min(f(n-1,insert),f(n-1,delete),f(n-1,replace))

now we know about how the function transfers, it’s time to look for the base case.

f(0, k) = f(k, 0) = k

f(pos1,pos2) means distance required to convert word1[:pos1] to word2[:pos2]

like the above pic, in order to change ab(word1) to ab(word2),there are three ways.

ab(w1)->a(w2) (insert b)

a(w1)->a(w2) (replace when the next are not equal)

a(w1)->ab(w2)(delete b)

reference: https://www.youtube.com/watch?v=We3YDTzNXEk

solutions:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ l1, l2 = len(word1)+1, len(word2)+1 dp = [[0 for _ in xrange(l2)] for _ in xrange(l1)] for i in xrange(l1): dp[i][0] = i for j in xrange(l2): dp[0][j] = j for i in xrange(1, l1): for j in xrange(1, l2): dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(word1[i-1]!=word2[j-1])) return dp[-1][-1] |