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

[Swift]LeetCode583.两个字符串的删除操作|DeleteOperationforTwoStrings

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

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

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

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

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

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: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea". 

Note:

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

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

示例 1:

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

说明:

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

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 = 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, lcs(word1, word2, i, j - 1, &cache), lcs(word1, word2, i - 1, j, &cache))
22         }
23         cache[i][j] = maxLenght
24         return maxLenght
25     }
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 * 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 }

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] = 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 }

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] = 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 }

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, word2, 0, 0, &memo)
 7     }
 8     
 9     func helper(_ word1: String, _ word2: String,_ p1:Int,_ p2:Int,_ memo:inout [[Int]]) -> Int
10     {
11         if memo[p1][p2] != 0
12         {
13             return memo[p1][p2]
14         }
15         var n1:Int = word1.count
16         var n2:Int = word2.count
17         if p1 == n1 || p2 == n2
18         {
19             return n1 - p1 + n2 - p2            
20         }
21         if word1[p1] == word2[p2]
22         {
23             memo[p1][p2] = helper(word1, word2, p1 + 1, p2 + 1, &memo)
24         }
25         else
26         {
27              memo[p1][p2] = 1 + min(helper(word1, word2, p1 + 1, p2, &memo), helper(word1, word2, p1, p2 + 1, &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 }

 

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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