[Swift]LeetCode1092.最短公共超序列|ShortestCommonSupersequence

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

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

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

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

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

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

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 =

Note:

1 <= str1.length, str2.length <= 1000
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 <= str1.length, str2.length <= 1000
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 }