मान लीजिए हमारे पास स्ट्रिंग्स की एक सरणी A है, हमें कोई भी सबसे छोटी स्ट्रिंग ढूंढनी है जो A में प्रत्येक स्ट्रिंग को सबस्ट्रिंग के रूप में समाहित करती है। हम यह भी मान सकते हैं कि A में कोई भी स्ट्रिंग A की किसी अन्य स्ट्रिंग का सबस्ट्रिंग नहीं है।
उदाहरण के लिए, यदि इनपुट ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] है, तो आउटपुट "hdsbbhssdbshdbsd" होगा।
हल करने का दृष्टिकोण
यह यात्रा विक्रेता समस्या (TSP) का एक रूपांतर है जिसमें DP और बिटमास्क का उपयोग होता है:
calc(a, b) = b को a के बाद जोड़ने पर अतिरिक्त लंबाई की गणना करें
सभी जोड़ियों के लिए ओवरलैप ग्राफ बनाएं
dp[mask][i] = मास्क द्वारा दर्शाए गए स्ट्रिंग्स को कवर करने वाली न्यूनतम लंबाई जो i पर समाप्त होती है
पथ पुनर्निर्माण के लिए पथ सरणी का उपयोग करें
सभी मास्क और अंतिम नोड्स पर पुनरावृति करें
इष्टतम पथ से सुपरस्ट्रिंग पुनर्निर्मित करें
उदाहरण
#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;
}
};
int main(){
Solution ob;
vector<string> v = {"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"};
cout << (ob.shortestSuperstring(v));
return 0;
}
इनपुट
{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}
आउटपुट
hdsbbhssdbshdbsd