[Swift]LeetCode72. 编辑距离 | Edit Distance

weixin_30371469

92人浏览 · 2018-11-08 10:44:00

weixin_30371469 · 2018-11-08 10:44:00 发布

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

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:

Insert a character
Delete a character
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:

输入: 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 }