首页 > itarticle > edit distance Idea Code

edit distance Idea Code

admin 1月 18, 2021 0

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

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

Examle

1
2
3
4
5
6
 
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Idea

这个问题是一个DP问题，它最终解的形式并不复杂，但是并不好想。
其实就是建立m*n的棋盘，对word1[:i]与word2[:j]的转换步DP[i][j]，共考虑四种情况：

  1. word1[i]与word2[j]匹配，则DP[i][j] = DP[i-1][j-1]
  2. word1插入
  3. word1替换
  4. word1删除

Code

空间复杂度O(mn)版本（速度也更慢）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
class :
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        l1 = len(word1)
        l2 = len(word2)
        r = [[0] * (l2 + 1) for i in range(l1 + 1)]
        for i in range(l1 + 1):
            r[i][0] = i
        for j in range(l2 + 1):
            r[0][j] = j
        for i in range(1, l1 + 1):
            for j in range(1, l2 + 1):
                if word1[i-1] == word2[j-1]:
                    r[i][j] = r[i-1][j-1]
                else:
                    r[i][j] = min(r[i-1][j-1] + 1, r[i-1][j] + 1, r[i][j-1] + 1)
        return r[l1][l2]

优化为空间复杂度O(min(m,n))，速度也会快（上边的Beats30%，下边的95%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
class :
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        l1 = len(word1)
        l2 = len(word2)
        if l1 == 0: return l2
        if l2 == 0 : return l1
        r = [0] * (l2 + 1)
        for j in range(l2 + 1):
            r[j] = j
        for i in range(1, l1 + 1):
            tmp = i
            for j in range(1, l2 + 1):
                if word1[i-1] == word2[j-1]:
                    tmp1 = r[j-1]
                else:
                    tmp1 = min(r[j-1] + 1, r[j] + 1, tmp + 1)
                r[j-1] = tmp
                tmp = tmp1
            r[l2] = tmp
        return r[l2]
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能