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

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

原作者: [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. 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 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
Swift的初认识发布时间:2022-07-13
下一篇:
[Swift]LeetCode265.粉刷房子II$PaintHouseII发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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