ধরুন আমাদের কাছে স্ট্রিংগুলির একটি অ্যারে রয়েছে, আমাদেরকে একটি সাবস্ট্রিং হিসাবে A-তে প্রতিটি স্ট্রিং ধারণ করে এমন যেকোনো ছোট স্ট্রিং খুঁজে বের করতে হবে। আমরা এটাও ধরে নিতে পারি যে A-এর কোনো স্ট্রিং A-তে অন্য কোনো স্ট্রিংয়ের সাবস্ট্রিং নয়।
সুতরাং, যদি ইনপুটটি ["dbsh","dsbbhs","hdsb","ssdb","bshdbsd"] এর মত হয়, তাহলে আউটপুট হবে "hdsbbhssdbshdbsd"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন calc() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি সূচী i থেকে শেষ পর্যন্ত a এর সাবস্ট্রিং b এর শুরুতে হয়, তাহলে −
-
b এর রিটার্ন সাইজ - a + i
এর সাইজ
-
-
-
বি
এর রিটার্ন সাইজ -
প্রধান পদ্ধতি থেকে, এই পদক্ষেপগুলি করুন
-
ret :=খালি স্ট্রিং
-
n :=A
এর আকার -
n x n −
আকারের একটি 2D অ্যারে গ্রাফ সংজ্ঞায়িত করুন-
j শুরু করার জন্য :=0, যখন j
করুন -
গ্রাফ[i, j] :=calc(A[i], A[j])
-
গ্রাফ[j, i] :=calc(A[j], A[i])
-
-
-
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:2^n x n।
-
আকারের একটি অ্যারে পথ সংজ্ঞায়িত করুন:2^n x n.
-
minVal :=inf
-
শেষ :=-1
-
আরম্ভ করার জন্য i :=0, যখন i <2^n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
করুন-
j শুরু করার জন্য :=0, যখন j
করুন -
dp[i, j] :=inf
-
-
-
আরম্ভ করার জন্য i :=0, যখন i <2^n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
করুন-
j শুরু করার জন্য :=0, যখন j
করুন -
যদি i AND 2^j অ-শূন্য হয়, তাহলে
-
পূর্ববর্তী :=i ^ (2^j)
-
-
যদি পূর্ববর্তী 0 এর মত হয়, তাহলে −
-
dp[i, j] :=A[j]
এর আকার
-
-
অন্যথায়
-
আরম্ভ করার জন্য k :=0, যখন k
-
যদি prev AND 2^k এবং df[prev,k] না হয় inf এবং df[prev,k] +graph[k,j]
-
dp[i, j] :=dp[prev, k] + গ্রাফ[k, j]
-
পথ[i, j] :=k
-
-
-
-
-
যদি i 2^n - 1 এবং dp[i, j]
-
minVal :=dp[i, j]
-
শেষ :=j
-
-
-
curr :=2^n - 1
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
যখন curr> 0, do −
-
st
-এ শেষ ঢোকান -
temp :=curr
-
curr :=curr - (2^শেষ)
-
শেষ :=পথ[অস্থায়ী, শেষ]
-
-
i :=st
এর শীর্ষ উপাদান -
st
থেকে উপাদান মুছুন -
ret :=ret + A[i]
-
যখন (st খালি নয়), −
করুন-
j :=st
এর শীর্ষ উপাদান -
st
থেকে উপাদান মুছুন -
ret :=A[j] এর ret concatenate সাবস্ট্রিং (A[j] - গ্রাফ[i,j] থেকে শেষ পর্যন্ত)
-
i :=j
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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)); }
ইনপুট
{"dbsh","dsbbhs","hdsb","ssdb","bshdbsd"}
আউটপুট
hdsbbhssdbshdbsd