[Swift]LeetCode712.两个字符串的最小ASCII删除和|MinimumASCIIDeleteSumforTwoString ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

注意:

0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之间。

Runtime: 196 ms

Memory Usage: 20 MB

 1 class Solution {
 2     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 3         var arr1:[Character] = Array(s1)
 4         var arr2:[Character] = Array(s2)
 5         var nums1:[Int] = arr1.map{$0.ascii}
 6         var nums2:[Int] = arr2.map{$0.ascii}
 7         var m:Int = s1.count
 8         var n:Int = s2.count
 9         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n + 1),count:m + 1)
10         for i in 1...m
11         {
12             for j in 1...n
13             {
14                 if arr1[i - 1] == arr2[j - 1]
15                 {
16                     dp[i][j] = dp[i - 1][j - 1] + nums1[i - 1]
17                 }
18                 else
19                 {
20                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
21                 }
22             }
23         }
24         var sum1:Int = nums1.reduce(0,+)
25         var sum2:Int = nums2.reduce(0,+)
26         return sum1 + sum2 - 2 * dp[m][n]
27     }
28 }
29 
30 //Character扩展 
31 extension Character  
32 {  
33   //Character转ASCII整数值(定义小写为整数值)
34    var ascii: Int {
35        get {
36            return Int(self.unicodeScalars.first?.value ?? 0)
37        }       
38     }    
39 }

200ms

 1 final class Solution {
 2     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 3         let s1 = Array(s1.utf8).map(Int.init)
 4         let s2 = Array(s2.utf8).map(Int.init)
 5         var dp = [[Int]](repeating: Array(repeating: 0, count: s2.count &+ 1), count: s1.count &+ 1)
 6         
 7         for i in 0..<s1.count {
 8             dp[i &+ 1][0] = dp[i][0] &+ s1[i]
 9         }
10         for j in 0..<s2.count {
11             dp[0][j &+ 1] = dp[0][j] &+ s2[j]
12         }
13         for i in 1..<s1.count &+ 1 {
14             for j in 1..<s2.count &+ 1 {
15                 if s1[i - 1] == s2[j - 1] {
16                     dp[i][j] = dp[i - 1][j - 1]
17                 } else {
18                     dp[i][j] = min(s2[j - 1] &+ dp[i][j - 1], s1[i - 1] &+ dp[i - 1][j])
19                 }
20             }
21         }
22         
23         return dp[s1.count][s2.count]
24     }
25 }

436ms

 1 class Solution {
 2     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 3        var v = 97
 4         var map = [Character: Int]()
 5        "abcdefghijklmnopqrstuvwxyz".map { map[$0] = v; v += 1}
 6         let m = s1.count, n = s2.count
 7         let chars1 = Array(s1), chars2 = Array(s2)
 8         var dp = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: m+1)
 9         for j in 1...n {
10             dp[0][j] = dp[0][j-1] + map[chars2[j-1]]!
11         }
12         for i in 1...m {
13             dp[i][0] = dp[i-1][0] + map[chars1[i-1]]!
14             for j in 1...n {
15                 if chars1[i-1] == chars2[j-1] {
16                     dp[i][j] = dp[i-1][j-1]
17                 }
18                 else {
19                     dp[i][j] = min(dp[i-1][j] + map[chars1[i-1]]!, dp[i][j-1] + map[chars2[j-1]]!)
20                 }
21             }
22         }
23         return dp[m][n]
24     }
25 }
26 
27 extension Character {
28     var ascii: Int {
29         return Int(unicodeScalars.first?.value ?? 0)
30     }
31 }

548ms

 1 class Solution {
 2     var map = [Character: Int]()
 3     var ans = Int.max
 4     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 5         var v = 97
 6        "abcdefghijklmnopqrstuvwxyz".map { map[$0] = v; v += 1}
 7         let m = s1.count, n = s2.count
 8         let chars1 = Array(s1), chars2 = Array(s2)
 9         var dp = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: m+1)
10         for j in 1...n {
11             dp[0][j] = dp[0][j-1] + map[chars2[j-1]]!
12         }
13         for i in 1...m {
14             dp[i][0] = dp[i-1][0] + map[chars1[i-1]]!
15             for j in 1...n {
16                 if chars1[i-1] == chars2[j-1] {
17                     dp[i][j] = dp[i-1][j-1]
18                 }
19                 else {
20                     dp[i][j] = min(dp[i-1][j] + map[chars1[i-1]]!, dp[i][j-1] + map[chars2[j-1]]!)
21                 }
22             }
23         }
24         return dp[m][n]
25     }
26 
27     func dfs(_ s1: [Character], _ index1: Int, _ s2: [Character], _ index2: Int, _ sum: Int) {
28                 
29         if sum > ans {
30             return
31         }
32 
33         if index1 >= s1.count && index2 >= s2.count {
34             ans = min(ans, sum)
35             return
36         }
37 
38         if index1 < s1.count && index2 < s2.count {
39 
40             if s1[index1] == s2[index2] {
41                 dfs(s1, index1+1, s2, index2+1, sum)
42                 return
43             }
44             dfs(s1, index1+1, s2, index2, sum + map[s1[index1]]!)
45             dfs(s1, index1, s2, index2+1, sum + map[s2[index2]]!)
46             dfs(s1, index1+1, s2, index2+1, sum + map[s2[index2]]! + map[s1[index1]]!)
47         }
48         else if index1 >= s1.count && index2 < s2.count {            
49             dfs(s1, index1, s2, index2+1, sum + map[s2[index2]]!)
50         }
51         else if index1 < s1.count && index2 >= s2.count {
52             dfs(s1, index1+1, s2, index2, sum + map[s1[index1]]!)
53         }
54     }
55 }

604ms

 1 class Solution {
 2     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 3     var mem = [[Int?]](repeating: [Int?](repeating: nil, count: s2.count + 1), count: s1.count + 1)
 4     return minimumDeleteSumRecursion(Array(s1), Array(s2), 0, s2Index: 0, mem: &mem)
 5 }
 6 
 7 func minimumDeleteSumRecursion(_ s1 : [Character], _ s2 : [Character], _ s1Index : Int, s2Index : Int, mem : inout [[Int?]])->Int{
 8     
 9     guard s1Index < s1.count || s2Index < s2.count else{
10         return 0
11     }
12     
13     if let answer = mem[s1Index][s2Index]{
14         return answer
15     }
16     
17     if s1Index == s1.count{
18         mem[s1Index][s2Index] = Int(s2[s2Index].unicodeScalars.first!.value) + minimumDeleteSumRecursion(s1, s2, s1Index, s2Index: s2Index + 1, mem: &mem)
19         return mem[s1Index][s2Index]!
20     }else if s2Index == s2.count{
21         mem[s1Index][s2Index] = Int(s1[s1Index].unicodeScalars.first!.value) + minimumDeleteSumRecursion(s1, s2, s1Index + 1, s2Index: s2Index, mem: &mem)
22         return mem[s1Index][s2Index]!
23     }else{
24         if s1[s1Index] == s2[s2Index]{
25             mem[s1Index][s2Index] = minimumDeleteSumRecursion(s1, s2, s1Index + 1, s2Index: s2Index + 1, mem: &mem)
26             return mem[s1Index][s2Index]!
27         }else{
28             // we need to delete
29             let firstValue = Int(s1[s1Index].unicodeScalars.first!.value) + minimumDeleteSumRecursion(s1, s2, s1Index + 1, s2Index: s2Index, mem: &mem)
30             let secondValue = Int(s2[s2Index].unicodeScalars.first!.value) + minimumDeleteSumRecursion(s1, s2, s1Index, s2Index: s2Index + 1, mem: &mem)
31             mem[s1Index][s2Index] = min(firstValue, secondValue)
32             return mem[s1Index][s2Index]!
33         }
34     }
35   }
36 }

632ms

 1 class Solution {
 2     func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
 3     let s1 = Array(s1)
 4     let s2 = Array(s2)
 5     var matrix = [[Int]](repeating: [Int](repeating: 0, count: s2.count + 1), count: s1.count + 1)
 6     for s1Index in (0..<s1.count).reversed(){
 7         matrix[s1Index][s2.count] = matrix[s1Index + 1][s2.count] +  Int(s1[s1Index].unicodeScalars.first!.value)
 8     }
 9     for s2Index in (0..<s2.count).reversed(){
10         matrix[s1.count][s2Index] = matrix[s1.count][s2Index + 1] +  Int(s2[s2Index].unicodeScalars.first!.value)
11     }
12     for s1Index in (0..<s1.count).reversed(){
13         for s2Index in (0..<s2.count).reversed(){
14             if s1[s1Index] == s2[s2Index]{
15                 matrix[s1Index][s2Index] = matrix[s1Index + 1][s2Index + 1]
16             }else{
17                 let firstValue = Int(s1[s1Index].unicodeScalars.first!.value) + matrix[s1Index + 1][s2Index]
18                 let secondValue = Int(s2[s2Index].unicodeScalars.first!.value) + matrix[s1Index][s2Index + 1]
19                 matrix[s1Index][s2Index] = min(firstValue, secondValue)
20             }
21         }
22     }
23     return matrix[0][0]
24     }
25 }