• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode72.编辑距离|EditDistance

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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

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')

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

40ms
 1 class Solution {
 2     func minDistance(_ word1: String, _ word2: String) -> Int {
 3         if word1.count == 0 {
 4             return word2.count
 5         }
 6         if word2.count == 0 {
 7             return word1.count
 8         }
 9 
10         let c1 = Array(word1)
11         let c2 = Array(word2)
12         var cache = [[Int]](repeating: [Int](repeating: -1, count: c2.count), count: c1.count)
13 
14         return match(c1, c2, 0, 0, &cache)
15     }
16 
17     fileprivate func match(_ c1: [Character], _ c2: [Character], _ i: Int, _ j: Int, _ cache: inout [[Int]]) -> Int {
18         if c1.count == i {
19             return c2.count - j
20         }
21         if c2.count == j {
22             return c1.count - i
23         }
24 
25         if cache[i][j] != -1 {
26             return cache[i][j]
27         }
28 
29         if c1[i] == c2[j] {
30             cache[i][j] = match(c1, c2, i + 1, j + 1, &cache)
31         } else {
32             let insert = match(c1, c2, i, j + 1, &cache)
33             let delete = match(c1, c2, i + 1, j, &cache)
34             let replace = match(c1, c2, i + 1, j + 1, &cache)
35 
36             cache[i][j] = min(min(insert, delete), replace) + 1
37         }
38 
39         return cache[i][j]
40     }
41 }

80ms

 1 class Solution {
 2     func minDistance(_ word1: String, _ word2: String) -> Int {
 3         var w1arr = Array(word1.characters)
 4         var w2arr = Array(word2.characters)
 5         var w1len  = w1arr.count
 6         var w2len = w2arr.count
 7         
 8         if(word1.isEmpty && word2.isEmpty) {
 9             return 0
10         }
11         if(word1.isEmpty) {
12             return word2.count
13         }
14         else if(word2.isEmpty) {
15             return word1.count
16         }
17         
18         var dp = Array(repeating:Array(repeating:0,count:w2len+1),count:w1len+1)
19     
20         for i in 0...w2len {
21             dp[0][i] = i
22         }
23         for i in 0...w1len {
24             dp[i][0] = i
25         }
26         
27         for idx1 in 1...w1len {
28             for idx2 in 1...w2len {
29                 var minChange = min(min(dp[idx1-1][idx2],dp[idx1-1][idx2-1]),dp[idx1][idx2-1])
30                 dp[idx1][idx2] = w1arr[idx1-1] == w2arr[idx2-1] ?  dp[idx1-1][idx2-1] : minChange + 1
31             }
32         }
33         
34         return dp[w1len][w2len]
35         
36     }
37 }

92ms

 1 class Solution {
 2     func minDistance(_ word1: String, _ word2: String) -> Int {
 3         var res = Array(repeating: Array(repeating: 0, count: word2.count + 1), count: word1.count + 1)
 4         let word1Array = Array(word1)
 5         let word2Array = Array(word2)
 6         for i in 0...word1.count {
 7             for j in 0...word2.count {
 8                 if i == 0 {
 9                     res[i][j] = j
10                 }else if j == 0 {
11                     res[i][j] = i
12                 }else if word1Array[i - 1] == word2Array[j - 1] {
13                     res[i][j] = res[i - 1][j - 1]
14                 }else {
15                     res[i][j] = min(res[i - 1][j - 1], min(res[i - 1][j], res[i][j - 1])) + 1
16                 }
17             }
18         }
19         return res[word1.count][word2.count]
20     }
21 }

120ms

 1 class Solution {
 2 //向word1插入:dp[i][j] = dp[i][j-1] + 1;
 3 //从word1删除:dp[i][j] = dp[i-1][j] + 1;
 4 //替换word1元素:dp[i][j] = dp[i-1][j-1] + 1;
 5     func minDistance(_ word1: String, _ word2: String) -> Int {
 6         
 7         let m = word1.count
 8         let n = word2.count
 9         
10         if m == 0 { return n }
11         if n == 0 { return m }
12         
13         let chars1 = Array(word1.characters)
14         let chars2 = Array(word2.characters)
15         
16         var f = [[Int]](repeating:[Int](repeating: 0, count: n + 1), count: m + 1)
17         
18         for i in 0...m {
19             f[i][0] = i
20         }
21         
22         for i in 0...n {
23             f[0][i] = i
24         }
25         
26         for i in 1...m {
27             for j in 1...n {
28                 
29                 if chars1[i - 1] == chars2[j - 1] {
30                     f[i][j] = f[i - 1][j - 1]
31                 } else {
32                     f[i][j] = min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1  
33                 }
34             }
35         }
36         
37         return f[m][n]
38     }
39 }

124ms

 1 class Solution {
 2     func minDistance(_ word1: String, _ word2: String) -> Int {
 3         let word1 = Array(word1.characters)
 4         let word2 = Array(word2.characters)
 5         let len1 = word1.count
 6         let len2 = word2.count
 7         var res = Array(repeating: Array(repeating: 0, count: len2+1), count: len1+1)
 8         // res[i][j] = (word1[i] == word2[j] ? res[i+1][j+1] : min(1+res[i][j+1], 1 + res[i+1][j+1], res[i+1][j]))
 9         var j = len2
10         while j >= 0 {
11             var i = len1
12             while i >= 0 {
13                 if j == len2 { 
14                     res[i][j] = (len1 - i) // Delete
15                 } else {
16                     if i == len1 {
17                         res[i][j] = (len2 - j) // Insert
18                     } else {
19                         res[i][j] = (word1[i] == word2[j] ? res[i+1][j+1] : min(1+res[i][j+1], 1+res[i+1][j+1], 1+res[i+1][j]))
20                     }
21                 }
22                 i -= 1
23             }
24             j -= 1
25         }
26         
27         return res[0][0]
28     }
29 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Facebook 针对 iOS 推出 Swift 开发者工具包发布时间:2022-07-13
下一篇:
Swift统计操作list container、show account结果为0的问题发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap