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

概述Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string. Example 1: Input: "sea",

Given two words word1 and word2,find the minimum number of steps required to make word1 and word2 the same,where in each step you can delete one character in either string.

Example 1:

input: "sea","eat"Output: 2Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea". 

Note:

The length of given words won‘t exceed 500. Characters in given words can only be lower-case letters.

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例 1:

输入: "sea","eat"输出: 2解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

说明:

给定单词的长度不超过500。 给定单词中的字符只含有小写字母。

124ms

 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 = 012         if i < 0 || j < 0 {13             return maxLenght14         }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] = maxLenght24         return maxLenght25     }26 }

132ms

 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 * len11     }12     13     func longestCommonSequence(_ string1: [Character],_ string2: [Character]) -> Int {14         let m = string1.count15         let n = string2.count16         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] + 126                 } 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 }

136ms

 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] = column13     }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]) + 121             }22         }23     }24     25     return dp.last!.last!26   }27 }

156ms

 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] = i13         }14         15         for i in 0 ... len2 {16             dp[0][i] = i17         }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 }

Runtime: 732 ms Memory Usage: 20.4 MB

 1 class Solution { 2     func mindistance(_ word1: String,_ word2: String) -> Int { 3         var n1:Int = word1.count 4         var n2:Int = word2.count 5         var memo:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n2 + 1),count:n1 + 1) 6         return helper(word1,0,&memo) 7     } 8      9     func helper(_ word1: String,_ word2: String,_ p1:Int,_ p2:Int,_ memo:inout [[Int]]) -> Int10     {11         if memo[p1][p2] != 012         {13             return memo[p1][p2]14         }15         var n1:Int = word1.count16         var n2:Int = word2.count17         if p1 == n1 || p2 == n218         {19             return n1 - p1 + n2 - p2            20         }21         if word1[p1] == word2[p2]22         {23             memo[p1][p2] = helper(word1,p1 + 1,p2 + 1,&memo)24         }25         else26         {27              memo[p1][p2] = 1 + min(helper(word1,p2,&memo),helper(word1,p1,&memo))28         }29         return memo[p1][p2]30     }31 }32 33 extension String {        34     //subscript函数可以检索数组中的值35     //直接按照索引方式截取指定索引的字符36     subscript (_ i: Int) -> Character {37         //读取字符38         get {return self[index(startIndex,offsetBy: i)]}39     }40 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode583. 两个字符串的删除 *** 作 | Delete Operation for Two Strings全部内容，希望文章能够帮你解决[Swift]LeetCode583. 两个字符串的删除 *** 作 | Delete Operation for Two Strings所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。