[Swift]LeetCode583. 两个字符串的删除操作 | Delete Operation for Two Strings

 1 class Solution {
 2     func minDistance(_ word1: String,_ word2: String) -> Int {
 3         if word1.count < word2.count {
 4             return minDistance(word2,word1)
 5         }
 6         var cache = Array(repeaTing: Array(repeaTing: -1,count: word2.count),count: word1.count)
 7         return word1.count + word2.count - lcs(Array(word1),Array(word2),word1.count - 1,word2.count - 1,&cachE)*2
 8     }
 9     
10     func lcs(_ word1:[Character],_ word2:[Character],_ i:Int,_ j:Int,_ cache:inout [[Int]]) -> Int {
11         var maxLenght = 0
12         if i < 0 || j < 0 {
13             return maxLenght
14         }
15         if cache[i][j] != -1 {
16             return cache[i][j]
17         }
18         if word1[i] == word2[j] {
19             maxLenght = max(maxLenght,lcs(word1,word2,i - 1,j - 1,&cachE) + 1)
20         } else {
21             maxLenght = max(maxLenght,i,&cachE),j,&cachE))
22         }
23         cache[i][j] = maxLenght
24         return maxLenght
25     }
26 }

 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         let len = longestCommonSequence(Array(word1),Array(word2))
10         return word1.count + word2.count - 2 * len
11     }
12     
13     func longestCommonSequence(_ String1: [Character],_ String2: [Character]) -> Int {
14         let m = String1.count
15         let n = String2.count
16         var dp = [[Int]]()
17         for _ in 0 ..< m + 1 {
18             let array = [Int].init(repeaTing: 0,count: n + 1)
19             dp.append(array)
20         }
21         
22         for i in 0 ..< m {
23             for j in 0 ..< n {
24                 if String1[i] == string2[j] {
25                     dp[i+1][j+1] = dp[i][j] + 1
26                 } else {
27                     dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
28                 }
29             }
30         }
31         return dp[m][n]
32     }
33 }

 1 class Solution {
 2     func minDistance(_ word1: String,_ word2: String) -> Int {
 3     var word1 = Array(word1)
 4     var word2 = Array(word2)
 5     var dp = [[Int]](repeaTing: [Int](repeaTing: 0,count: word2.count + 1),count: word1.count + 1)
 6     
 7     for row in 0..<dp.count{
 8         dp[row][0] = row
 9     }
10     
11     for column in 0..<dp[0].count{
12         dp[0][column] = column
13     }
14     
15     for row in 1..<dp.count{
16         for column in 1..<dp[row].count{
17             if word1[row-1] == word2[column-1]{
18                 dp[row][column] = dp[row - 1][column - 1]
19             }else{
20                 dp[row][column] = min(dp[row - 1][column],dp[row][column - 1]) + 1
21             }
22         }
23     }
24     
25     return dp.last!.last!
26   }
27 }

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