前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 72. Edit Distance

leetcode: 72. Edit Distance

作者头像
JNingWei
发布2018-09-27 16:59:36
7590
发布2018-09-27 16:59:36
举报
文章被收录于专栏:JNing的专栏

Problem

代码语言:javascript
复制
# 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

Idea 1

From [LeetCode] Edit Distance

代码语言:javascript
复制
思路:

很多算法教科书上都有的经典二维DP问题。

1. 状态:
DP[i+1][j+1]:word1[0:i] -> word2[0:j]的edit distance。

2. 通项公式:
考虑word1[0:i] -> word2[0:j]的最后一次edit。无非题目中给出的三种方式:

a) 插入一个字符:word1[0:i] -> word2[0:j-1],然后在word1[0:i]后插入word2[j]
DP[i+1][j+1] = DP[i+1][j]+1

b) 删除一个字符:word1[0:i-1] -> word2[0:j],然后删除word1[i]
DP[i+1][j+1] = DP[i][j+1]+1

c) 替换一个字符:word1[0:i-1] -> word2[0:j-1]
word1[i] != word2[j]时,word1[i] -> word2[j]:DP[i+1][j+1] = DP[i][j] + 1
word1[i] == word2[j]时:DP[i+1][j+1] = DP[i][j] 

所以min editor distance应该为:
DP[i+1][j+1] = min(DP[i][j] + k, DP[i+1][j]+1, DP[i][j+1]+1) 
word1[i]==word2[j] -> k = 0, 否则k = 1

3. 计算方向:
replace (i, j)      delete (i, j+1)
insert (i+1, j)    (i+1, j+1)

可见要求DP[i+1][j+1],必须要知道二维矩阵中左上,上方和下方的3个值。所以当我们确定第0行和第0列的值后,就可以从上到下、从左到右的计算了。

4. 起始、边界值
DP[0][i] = i: word1为空,要转化到word2[0:i-1],需要添加i个字符。
DP[i][0] = i: word2为空,要从word1转化到空字符串,需要删除i个字符。

Idea 2

From [LeetCode] Edit Distance 编辑距离

代码语言:javascript
复制
这道题让求从一个字符串转变到另一个字符串需要的变换步骤,共有三种变换方式,插入一个字符,删除一个字符,和替换一个字符。
根据以往的经验,对于字符串相关的题目十有八九都是用动态规划Dynamic Programming来解,这道题也不例外。

跟以往的DP题目类似,难点还是在于找出递推式。

这道题我们需要维护一个二维的数组dp,其中dp[i][j]表示从word1的前i个字符转换到word2的前j个字符所需要的步骤。

比如word1是“bbc”,word2是”abcd“,那么我们可以得到dp数组如下:

  Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2

我们通过观察可以发现,当word1[i] == word2[j]时,dp[i][j] = dp[i - 1][j - 1],其他情况时,dp[i][j]是其左,左上,上的三个值中的最小值加1,那么可以得到递推式为:

if word1[i - 1] == word2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]                                                                   
else:
    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1            

AC

代码语言:javascript
复制
class Solution():
    def minDistance(self, word1, word2):
        distance = [[i] for i in range(len(word1) + 1)]
        distance[0] = [j for j in range(len(word2) + 1)]
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                insert = distance[i][j - 1] + 1
                delete = distance[i - 1][j] + 1
                replace = distance[i - 1][j - 1] if word1[i - 1] == word2[j - 1] else distance[i - 1][j - 1] + 1
                distance[i].append(min(insert, delete, replace))
        return distance[-1][-1]


# Time:  O(n * m)
# Space: O(n + m)
class Solution():
    def minDistance(self, word1, word2):
        if len(word1) < len(word2):
            return self.minDistance(word2, word1)
        distance = [i for i in range(len(word2) + 1)]
        for i in range(1, len(word1) + 1):
            pre_distance_i_j = distance[0]
            distance[0] = i
            for j in range(1, len(word2) + 1):
                insert = distance[j - 1] + 1
                delete = distance[j] + 1
                replace = pre_distance_i_j
                if word1[i - 1] != word2[j - 1]:
                    replace += 1
                pre_distance_i_j = distance[j]
                distance[j] = min(insert, delete, replace)
        return distance[-1]


if __name__ == "__main__":
    assert Solution().minDistance("Rabbit", "Racket") == 3
    assert Solution().minDistance("Rabbit", "Rabbt") == 1
    assert Solution().minDistance("Rabbit", "Rabbitt") == 1
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月20日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem
    • Idea 1
      • Idea 2
      • AC
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档