Skip to content

Commit 9fe643a

Browse files
liuyuboboboliuyubobobo
committed
0943 solved.
1 parent 48f3c4a commit 9fe643a

File tree

4 files changed

+205
-1
lines changed

4 files changed

+205
-1
lines changed

‎0943-Find-the-Shortest-Superstring/cpp-0943/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.12)
2+
project(D)
3+
4+
set(CMAKE_CXX_STANDARD 11)
5+
6+
add_executable(D main2.cpp)

‎0943-Find-the-Shortest-Superstring/cpp-0943/main.cpp

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
/// Source : https://leetcode.com/problems/find-the-shortest-superstring/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-11-17
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <unordered_map>
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
13+
/// Memory Search
14+
/// Time Complexity: O(2^n * n * n)
15+
/// Space Complexity: O(2^n * n)
16+
class Solution {
17+
18+
private:
19+
int n;
20+
unordered_map<int, string> dp;
21+
22+
public:
23+
string shortestSuperstring(vector<string>& A) {
24+
25+
dp.clear();
26+
n = A.size();
27+
28+
int best = INT_MAX;
29+
string res = "";
30+
for(int i = 0; i < n; i ++){
31+
string tres = dfs(A, 0, i);
32+
if(tres.size() < best){
33+
best = tres.size();
34+
res = tres;
35+
}
36+
}
37+
return res;
38+
}
39+
40+
private:
41+
string dfs(const vector<string>& A, int state, int index){
42+
43+
if(state == (1 << n) - 1 - (1 << index))
44+
return A[index];
45+
46+
int hash = state * 100 + index;
47+
if(dp.count(hash))
48+
return dp[hash];
49+
50+
state |= (1 << index);
51+
52+
int best = INT_MAX;
53+
string res;
54+
for(int i = 0; i < n; i ++)
55+
if((state & (1 << i)) == 0){
56+
string tres = dfs(A, state, i);
57+
for(int len = min(tres.size(), A[index].size()); len >= 0; len --)
58+
if(tres.substr(tres.size() - len, len) == A[index].substr(0, len)){
59+
tres += A[index].substr(len);
60+
break;
61+
}
62+
63+
if(tres.size() < best){
64+
best = tres.size();
65+
res = tres;
66+
}
67+
}
68+
return dp[hash] = res;
69+
}
70+
};
71+
72+
73+
int main() {
74+
75+
vector<string> A1 = {"alex","loves","leetcode"};
76+
string res1 = Solution().shortestSuperstring(A1);
77+
cout << res1 << endl;
78+
string ans1 = "alexlovesleetcode";
79+
assert(ans1.size() == res1.size());
80+
81+
82+
vector<string> A2 = {"wmiy","yarn","rnnwc","arnnw","wcj"};
83+
string res2 = Solution().shortestSuperstring(A2);
84+
cout << res2 << endl;
85+
string ans2 = "wmiyarnnwcj";
86+
assert(ans2.size() == res2.size());
87+
88+
89+
vector<string> A3 = {"chakgmeinq","lhdbntkf","mhkelhye","hdbntkfch","kfchakgme","wymhkelh","kgmeinqw"};
90+
string res3 = Solution().shortestSuperstring(A3);
91+
cout << res3 << endl;
92+
string ans3 = "lhdbntkfchakgmeinqwymhkelhye";
93+
assert(ans3.size() == res3.size());
94+
95+
return 0;
96+
}

‎0943-Find-the-Shortest-Superstring/cpp-0943/main2.cpp

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
/// Source : https://leetcode.com/problems/find-the-shortest-superstring/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-11-17
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <unordered_map>
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
13+
/// Memory Search
14+
/// Pre-calculate overlapped to improve the performance
15+
///
16+
/// Time Complexity: O(2^n * n * n)
17+
/// Space Complexity: O(2^n * n)
18+
class Solution {
19+
20+
private:
21+
int n;
22+
unordered_map<int, string> dp;
23+
24+
public:
25+
string shortestSuperstring(vector<string>& A) {
26+
27+
dp.clear();
28+
n = A.size();
29+
30+
vector<vector<int>> overlaped(n, vector<int>(n));
31+
for(int i = 0; i < n; i ++)
32+
for(int j = 0; j < n; j ++)
33+
for(int len = min(A[i].size(), A[j].size()); len >= 0; len --)
34+
if(A[i].substr(A[i].size() - len, len) == A[j].substr(0, len)){
35+
overlaped[i][j] = len;
36+
break;
37+
}
38+
39+
int best = INT_MAX;
40+
string res = "";
41+
for(int i = 0; i < n; i ++){
42+
string tres = dfs(A, 0, i, overlaped);
43+
if(tres.size() < best){
44+
best = tres.size();
45+
res = tres;
46+
}
47+
}
48+
return res;
49+
}
50+
51+
private:
52+
string dfs(const vector<string>& A, int state, int index, const vector<vector<int>>& overlapped){
53+
54+
if(state == (1 << n) - 1 - (1 << index))
55+
return A[index];
56+
57+
int hash = state * 100 + index;
58+
if(dp.count(hash))
59+
return dp[hash];
60+
61+
state |= (1 << index);
62+
63+
int best = INT_MAX;
64+
string res;
65+
for(int i = 0; i < n; i ++)
66+
if((state & (1 << i)) == 0){
67+
string tres = dfs(A, state, i, overlapped);
68+
tres += A[index].substr(overlapped[i][index]);
69+
if(tres.size() < best){
70+
best = tres.size();
71+
res = tres;
72+
}
73+
}
74+
return dp[hash] = res;
75+
}
76+
};
77+
78+
79+
int main() {
80+
81+
vector<string> A1 = {"alex","loves","leetcode"};
82+
string res1 = Solution().shortestSuperstring(A1);
83+
cout << res1 << endl;
84+
string ans1 = "alexlovesleetcode";
85+
assert(ans1.size() == res1.size());
86+
87+
88+
vector<string> A2 = {"wmiy","yarn","rnnwc","arnnw","wcj"};
89+
string res2 = Solution().shortestSuperstring(A2);
90+
cout << res2 << endl;
91+
string ans2 = "wmiyarnnwcj";
92+
assert(ans2.size() == res2.size());
93+
94+
95+
vector<string> A3 = {"chakgmeinq","lhdbntkf","mhkelhye","hdbntkfch","kfchakgme","wymhkelh","kgmeinqw"};
96+
string res3 = Solution().shortestSuperstring(A3);
97+
cout << res3 << endl;
98+
string ans3 = "lhdbntkfchakgmeinqwymhkelhye";
99+
assert(ans3.size() == res3.size());
100+
101+
return 0;
102+
}

‎readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -598,6 +598,6 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
598598
| 940 | [Distinct Subsequences II](https://leetcode.com/problems/distinct-subsequences-ii/) | [solution](https://leetcode.com/problems/distinct-subsequences-ii/solution/) | [C++](0940-Distinct-Subsequences-II/cpp-0940/) | | |
599599
| 941 | [Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/) | [solution](https://leetcode.com/problems/valid-mountain-array/solution/) | [C++](0941-Valid-Mountain-Array/cpp-0941/) | | |
600600
| 942 | [DI String Match](https://leetcode.com/problems/di-string-match/) | [solution](https://leetcode.com/problems/di-string-match/solution/) | [C++](0942-DI-String-Match/cpp-0942/) | | |
601-
| | | | | | |
601+
| 943 | [Find the Shortest Superstring](https://leetcode.com/problems/find-the-shortest-superstring/) | [solution](https://leetcode.com/problems/find-the-shortest-superstring/solution/)<br/>[缺：动态规划] | [C++](0943-Find-the-Shortest-Superstring/cpp-0943/) | | |
602602
| 944 | [Delete Columns to Make Sorted](https://leetcode.com/problems/delete-columns-to-make-sorted/) | [solution](https://leetcode.com/problems/delete-columns-to-make-sorted/solution/) | [C++](0944-Delete-Columns-to-Make-Sorted/cpp-0944/) | | |
603603
| | | | | | |

0 commit comments

Comments
 (0)