首页 > 其他 > 详细

[LeetCode] 72. Edit Distance_hard tag: Dynamic Programming

时间:2018-07-20 00:58:00      阅读:245      评论:0      收藏:0      [点我收藏+]

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

You have the following 3 operations permitted on a word:

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

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace ‘h‘ with ‘r‘)
rorse -> rose (remove ‘r‘)
rose -> ros (remove ‘e‘)

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove ‘t‘)
inention -> enention (replace ‘i‘ with ‘e‘)
enention -> exention (replace ‘n‘ with ‘x‘)
exention -> exection (replace ‘n‘ with ‘c‘)
exection -> execution (insert ‘u‘)

这个题目思路是用Dynamic Programming, ans[i][j] 表明前i-1 个word1的字符与到前j-1个word2的
字符的最小值, 然后ans[i][j] = min(ans[i-1][j]+ 1, ans[i][j-1] + 1, ans[i-1][j-1] + temp)
其中temp = 1 if word1[i] == word2[j] else 0
最后返回ans[m,n]即可. 这个模式跟[LeetCode] 221. Maximal Square _ Medium Tag: Dynamic Programming
很像, 都是用上, 左和左上角的元素去递推现在的元素. 当然也可以用滚动数组的方式去将space 降为 O(n)

1. Constraints
1) size >= [0*0]
2) element can be anything, captal sensitive

2. ideas
Dynamic programming, T: O(m*n) S: O(m*n) => O(n) using rolling array

3. Codes
1) S: O(m*n)
 1 class Solution:
 2     def editDistance(self, word1, word2):
 3         m, n = len(word1), len(word2)
 4         ans = [[0]*n+1 for _ in range(m+1)]
 5         for i in range(1, m+1):
 6             ans[i][0] = i
 7         for j in range(1, n+1):
 8             ans[0][j] = j
 9         for i in range(1, m+1):
10             for j in range(1, n+1):
11                 temp = 1 if word1[i] == word2[j] else 0
12                 ans[i][j] = min(ans[i-1][j] + 1, ans[i][j-1] + 1, ans[i-1][j-1] + temp)
13         return ans[m][n]

 

2) S: O(n) using 滚动数组

 1 class Solution:
 2     def editDistance(self, word1, word2):
 3         m, n = len(word1), len(word2)
 4         ans = [[0]*(n+1) for _ in range(2)]
 5         for j in range(1, n+1):
 6             ans[0][j] = j
 7         ans[1][0] = 1
 8         for i in range(1, m+1):
 9             for j in range(1, n+1):
10                 ans[i%2][0] = i
11                 temp = 0 if word1[i] == word2[j] else 1
12                 ans[i%2][j] = min(ans[i%2-1][j] + 1, ans[i%2][j-1] + 1, ans[i%2-1][j-1] + temp)
13         return ans[m%2][n]

 

4. Test cases

1)  "horse", "ros"

 




[LeetCode] 72. Edit Distance_hard tag: Dynamic Programming

原文:https://www.cnblogs.com/Johnsonxiong/p/9339160.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!