[Swift]LeetCode943. 最短超级串 | Find the Shortest Superstring
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10015724.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given an array A of strings, find any smallest string that contains each string in A as a substring.
We may assume that no string in A is substring of another string in A.
Example 1:
Input: ["alex","loves","leetcode"] Output: "alexlovesleetcode" Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"] Output: "gctaagttcatgcatc"
Note:
1 <= A.length <= 121 <= A[i].length <= 20
给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。
我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。
示例 1：
输入：["alex","loves","leetcode"] 输出："alexlovesleetcode" 解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：
输入：["catg","ctaagt","gcta","ttca","atgcatc"] 输出："gctaagttcatgcatc"
提示：
1 <= A.length <= 121 <= A[i].length <= 20
100ms
1 class Solution {
2 func countSubstr(_ A: [String], _ n: String) -> Int {
3 var sum = 0
4 for var s in A {
5 if n.contains(s) {
6 sum += s.count
7 }
8 }
9 return sum
10 }
11 func shortestSuperstring(_ Ain: [String]) -> String {
12 var A = Ain
13 while A.count > 1 {
14 var maxC = 0
15 var newStr = ""
16 for var i in 0..<A.count {
17 for var j in 0..<A.count {
18 guard i != j else {
19 continue
20 }
21 if A[i].count == 1 { continue }
22 for var l in 1...A[i].count-1 {
23 if A[j].hasPrefix(A[i].suffix(l)) {
24 let n = A[i] + A[j].suffix(A[j].count - l)
25 let C = countSubstr(A, n) - n.count
26 if C > maxC {
27 maxC = C
28 newStr = n
29 }
30 }
31 }
32 }
33 }
34 if maxC == 0 {
35 newStr = A[0] + A[1]
36 }
37 A.removeAll(where: { newStr.contains($0) })
38 A.append(newStr)
39 }
40 return A[0]
41 }
42 }
43
44 extension String {
45 func contains(_ find: String) -> Bool{
46 return self.range(of: find) != nil
47 }
48 }364ms
1 class Solution {
2 func shortestSuperstring(_ A: [String]) -> String {
3 var N:Int = A.count
4
5 // Populate overlaps
6 var overlaps:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:N),count:N)
7 for i in 0..<N
8 {
9 for j in 0..<N
10 {
11 if i != j
12 {
13 var m:Int = min(A[i].count, A[j].count)
14 for k in (0...m).reversed()
15 {
16 if A[i].hasSuffix(A[j].substring(0, k))
17 {
18 overlaps[i][j] = k
19 break
20 }
21 }
22 }
23 }
24 }
25 // dp[mask][i] = most overlap with mask, ending with ith element
26 var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:N),count:1<<N)
27 var parent:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:N),count:1<<N)
28 for mask in 0..<(1<<N)
29 {
30 for bit in 0..<N
31 {
32 if ((mask >> bit) & 1) > 0
33 {
34 // Let\'s try to find dp[mask][bit]. Previously, we had
35 // a collection of items represented by pmask.
36 var pmask:Int = mask ^ (1 << bit)
37 if pmask == 0 {continue}
38 for i in 0..<N
39 {
40 if ((pmask >> i) & 1) > 0
41 {
42 // For each bit i in pmask, calculate the value
43 // if we ended with word i, then added word \'bit\'.
44 var val:Int = dp[pmask][i] + overlaps[i][bit]
45 if val > dp[mask][bit]
46 {
47 dp[mask][bit] = val
48 parent[mask][bit] = i
49 }
50 }
51 }
52 }
53 }
54 }
55 // # Answer will have length sum(len(A[i]) for i) - max(dp[-1])
56 // Reconstruct answer, first as a sequence \'perm\' representing
57 // the indices of each word from left to right.
58 var perm:[Int] = [Int](repeating:0,count:N)
59 var seen:[Bool] = [Bool](repeating:false,count:N)
60 var t:Int = 0
61 var mask:Int = (1 << N) - 1
62
63 // p: the last element of perm (last word written left to right)
64 var p:Int = 0
65 for j in 0..<N
66 {
67 if dp[(1<<N) - 1][j] > dp[(1<<N) - 1][p]
68 {
69 p = j
70 }
71 }
72
73 // Follow parents down backwards path that retains maximum overlap
74 while (p != -1)
75 {
76 perm[t] = p
77 t += 1
78 seen[p] = true
79 var p2:Int = parent[mask][p]
80 mask ^= 1 << p
81 p = p2
82 }
83
84 // Reverse perm
85 for i in 0..<(t/2)
86 {
87 var v:Int = perm[i]
88 perm[i] = perm[t-1-i]
89 perm[t-1-i] = v
90 }
91
92 // Fill in remaining words not yet added
93 for i in 0..<N
94 {
95 if !seen[i]
96 {
97 perm[t] = i
98 t += 1
99 }
100 }
101
102 // Reconstruct final answer given perm
103 var ans:String = String(A[perm[0]])
104 for i in 1..<N
105 {
106 var overlap:Int = overlaps[perm[i-1]][perm[i]]
107 ans.append(A[perm[i]].substring(overlap))
108 }
109 return ans
110 }
111 }
112
113 extension String {
114 // 截取字符串：从index到结束处
115 // - Parameter index: 开始索引
116 // - Returns: 子字符串
117 func substring(_ index: Int) -> String {
118 let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
119 return String(self[theIndex..<endIndex])
120 }
121
122 // 截取字符串：指定索引和字符数
123 // - begin: 开始截取处索引
124 // - count: 截取的字符数量
125 func substring(_ begin:Int,_ count:Int) -> String {
126 let start = self.index(self.startIndex, offsetBy: max(0, begin))
127 let end = self.index(self.startIndex, offsetBy: min(self.count, begin + count))
128 return String(self[start..<end])
129 }
130 }