[Swift]LeetCode1092. 最短公共超序列 | Shortest Common Supersequence

我会带着你远行 2021-11-16 07:24 110阅读 0赞

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

Given two strings `str1` and `str2`, return the shortest string that has both `str1` and `str2` as subsequences.  If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab" Output: "cabac" Explanation: str1 = "abac" is a substring of "cabac" because we can delete the first "c". str2 = "cab" is a substring of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.

Note:

1.  `1 <= str1.length, str2.length <= 1000`
2.  `str1` and `str2` consist of lowercase English letters.

--------------------

给出两个字符串 `str1` 和 `str2`，返回同时以 `str1` 和 `str2` 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

示例：

输入：str1 = "abac", str2 = "cab"
    输出："cabac"
    解释：
    str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
    str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
    最终我们给出的答案是满足上述属性的最短字符串。

提示：

1.  `1 <= str1.length, str2.length <= 1000`
2.  `str1` 和 `str2` 都由小写英文字母组成。

--------------------

212ms

1 class Solution {
     2     func shortestCommonSupersequence(_ str1: String, _ str2: String) -> String {
     3         let matrix = lcsLength(str1, str2)
     4         let comSubseq = backtrack(matrix, str1, str2)
     5         var chars1 = Array(str1)
     6         var chars2 = Array(str2)
     7         var i = 0 
     8         var j = 0
     9         var result = ""
    10         for c in comSubseq {
    11             while chars1[i] != c {
    12                 result += String(chars1[i])
    13                 i += 1
    14             }
    15             i += 1
    16             while chars2[j] != c {
    17                 result += String(chars2[j])
    18                 j += 1
    19             }
    20             j += 1
    21             result += String(c)
    22         }
    23         while i < chars1.count {
    24             result += String(chars1[i])
    25             i += 1
    26         }
    27         while j < chars2.count {
    28             result += String(chars2[j])
    29             j += 1
    30         }
    31         return result
    32     }
    33     
    34     
    35     fileprivate func lcsLength(_ str1: String, _ str2: String) -> [[Int]] {
    36 
    37         var matrix = [[Int]](repeating: [Int](repeating: 0, count: str2.count+1), count: str1.count+1)
    38         for (i, str1Char) in str1.enumerated() {
    39             for (j, str2Char) in str2.enumerated() {
    40                 if str2Char == str1Char {
    41                     matrix[i+1][j+1] = matrix[i][j] + 1
    42                 } else {
    43                     matrix[i+1][j+1] = max(matrix[i][j+1], matrix[i+1][j])
    44                 }
    45             }
    46         }
    47         return matrix
    48     }
    49         
    50         
    51     fileprivate func backtrack(_ matrix: [[Int]], _ str1:String, _ str2: String) -> String {
    52         var i = str1.count
    53         var j = str2.count
    54         var charInSequence = str1.endIndex
    55         var lcs = String()
    56         while i >= 1 && j >= 1 {
    57             if matrix[i][j] == matrix[i][j - 1] {
    58                 j -= 1
    59             } else if matrix[i][j] == matrix[i - 1][j] {
    60                 i -= 1
    61                 charInSequence = str1.index(before: charInSequence)
    62             } else {
    63                 i -= 1
    64                 j -= 1
    65                 charInSequence = str1.index(before: charInSequence)
    66                 lcs.append(str1[charInSequence])
    67             }
    68         }
    69         return String(lcs.reversed())
    70     }
    71 }

--------------------

Runtime: 528 ms

Memory Usage: 28.8 MB

1 class Solution {
     2     var dp:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:1010),count:1010)
     3     var s1:[Character] = [Character]()
     4     var s2:[Character] = [Character]()
     5     
     6     func shortestCommonSupersequence(_ str1: String, _ str2: String) -> String {
     7         self.s1 = Array(str1)
     8         self.s2 = Array(str2)
     9         var r:String = String()
    10         rec(0, 0, &r)
    11         return r
    12     }
    13     
    14     func dfs(_ x:Int,_ y:Int) -> Int
    15     {
    16         if x == s1.count && y == s2.count
    17         {
    18             return 0
    19         }
    20         if dp[x][y] != -1 {
         return dp[x][y]}
    21         var ans:Int = Int(1e9)
    22         if x < s1.count
    23         {
    24             ans = min(ans, dfs(x+1, y) + 1)
    25         }
    26         if y < s2.count
    27         {
    28             ans = min(ans, dfs(x, y+1) + 1)
    29         }
    30         if x < s1.count && y < s2.count && s1[x] == s2[y]
    31         {
    32             ans = min(ans, dfs(x+1, y+1) + 1)
    33         }
    34         dp[x][y] = ans
    35         return ans
    36     }
    37     
    38     func rec(_ x:Int,_ y:Int,_ r:inout String)
    39     {
    40         if x == s1.count && y == s2.count
    41         {
    42             return
    43         }
    44         if x < s1.count
    45         {
    46             if dfs(x+1, y) + 1 == dfs(x,y)
    47             {
    48                 r.append(s1[x])
    49                 rec(x+1, y, &r)
    50                 return
    51             }
    52         }
    53         if y < s2.count
    54         {
    55             if dfs(x, y+1) + 1 == dfs(x,y)
    56             {
    57                 r.append(s2[y])
    58                 rec(x, y+1, &r)
    59                 return
    60             }
    61         }
    62         if x < s1.count && y < s2.count && s1[x] == s2[y]
    63         {
    64             if dfs(x+1, y+1) + 1 == dfs(x,y)
    65             {
    66                 r.append(s2[y])
    67                 rec(x+1, y+1, &r)
    68                 return
    69             }
    70         }
    71         return
    72     }
    73 }

转载于:https://www.cnblogs.com/strengthen/p/11014399.html

[https_www.cnblogs.com_strengthen]: https://www.cnblogs.com/strengthen/
[https_github.com_strengthen_LeetCode]: https://github.com/strengthen/LeetCode
[https_www.cnblogs.com_strengthen_p_11014399.html]: https://www.cnblogs.com/strengthen/p/11014399.html