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 }