Giả sử chúng ta có một mảng A gồm các chuỗi, chúng ta phải tìm bất kỳ chuỗi nhỏ nhất nào chứa mỗi chuỗi trong A là một chuỗi con. Chúng ta cũng có thể giả định rằng không có chuỗi nào trong A là chuỗi con của một chuỗi khác trong A.
Vì vậy, nếu đầu vào là ["dbsh", "dsbbhs", "hdsb", "ssdb", "bshdbsd"], thì đầu ra sẽ là "hdsbbhssdbshdbsd"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm calc (), điều này sẽ nhận a, b,
-
để khởi tạo i:=0, khi i
-
nếu chuỗi con của a từ chỉ mục i đến kết thúc nằm ở đầu của b, thì -
-
trả về kích thước của b - kích thước của a + i
-
-
-
kích thước trả về của b
-
Từ phương thức chính, hãy thực hiện các bước sau
-
ret:=chuỗi trống
-
n:=kích thước của A
-
Xác định một đồ thị mảng 2D có kích thước n x n -
-
để khởi tạo j:=0, khi j
-
graph [i, j]:=calc (A [i], A [j])
-
graph [j, i]:=calc (A [j], A [i])
-
-
-
Xác định một mảng dp có kích thước:2 ^ n x n.
-
Xác định đường dẫn mảng có kích thước:2 ^ n x n.
-
minVal:=inf
-
cuối cùng:=-1
-
để khởi tạo i:=0, khi tôi <2 ^ n, cập nhật (tăng i lên 1), thực hiện -
-
để khởi tạo j:=0, khi j
-
dp [i, j]:=inf
-
-
-
để khởi tạo i:=0, khi tôi <2 ^ n, cập nhật (tăng i lên 1), thực hiện -
-
để khởi tạo j:=0, khi j
-
nếu i VÀ 2 ^ j khác 0 thì
-
trước:=i ^ (2 ^ j)
-
-
nếu trước đây giống 0, thì -
-
dp [i, j]:=kích thước của A [j]
-
-
Nếu không
-
để khởi tạo k:=0, khi k
-
nếu trước và 2 ^ k và df [trước, k] không phải là inf và df [trước, k] + đồ thị [k, j]
-
dp [i, j]:=dp [pres, k] + graph [k, j]
-
đường dẫn [i, j]:=k
-
-
-
-
-
nếu tôi giống với 2 ^ n - 1 và dp [i, j]
-
minVal:=dp [i, j]
-
cuối cùng:=j
-
-
-
curr:=2 ^ n - 1
-
Xác định một ngăn xếp
-
while curr> 0, do -
-
chèn cuối cùng vào st
-
temp:=curr
-
curr:=curr - (2 ^ cuối)
-
last:=path [temp, last]
-
-
i:=phần tử hàng đầu của st
-
xóa phần tử khỏi st
-
ret:=ret + A [i]
-
while (not st là trống), do -
-
j:=phần tử hàng đầu của st
-
xóa phần tử khỏi st
-
ret:=ret nối chuỗi con của A [j] từ (kích thước của A [j] - graph [i, j] to end)
-
i:=j
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int calc(string& a, string& b){
for (int i = 0; i < a.size(); i++) {
if (b.find(a.substr(i)) == 0) {
return b.size() - a.size() + i;
}
}
return (int)b.size();
}
string shortestSuperstring(vector<string>& A){
string ret = "";
int n = A.size();
vector<vector<int> > graph(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = calc(A[i], A[j]);
graph[j][i] = calc(A[j], A[i]);
}
}
int dp[1 << n][n];
int path[1 << n][n];
int minVal = INT_MAX;
int last = -1;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = INT_MAX;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j))) {
int prev = i ^ (1 << j);
if (prev == 0) {
dp[i][j] = A[j].size();
} else {
for (int k = 0; k < n; k++) {
if ((prev & (1 << k)) && dp[prev][k] !=
INT_MAX && dp[prev][k] + graph[k][j] < dp[i][j]) {
dp[i][j] = dp[prev][k] + graph[k][j];
path[i][j] = k;
}
}
}
}
if (i == (1 << n) - 1 && dp[i][j] < minVal) {
minVal = dp[i][j];
last = j;
}
}
}
int curr = (1 << n) - 1;
stack<int> st;
while (curr > 0) {
st.push(last);
int temp = curr;
curr -= (1 << last);
last = path[temp][last];
}
int i = st.top();
st.pop();
ret += A[i];
while (!st.empty()) {
int j = st.top();
st.pop();
ret += (A[j].substr(A[j].size() - graph[i][j]));
i = j;
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
cout << (ob.shortestSuperstring(v));
} Đầu vào
{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"} Đầu ra
hdsbbhssdbshdbsd