Not able to figure out the bug in my code or the approach is wrong…
Approach:
I have sorted the strings given in the input.
Then, I precompute the cost it takes to merge 2 strings.
Cost[i][j] - cost to merge string ‘i’ and string ‘j’. Formally, It is essentially the smallest length of string ‘j’ which we need to take to merge string ‘i’ and string ‘j’.
Dp state -
mask - bit representation of the strings i have selected so far
last - the last chosen string
While printing the answer i make sure to take the lexicographically smallest option as i have already sorted the strings.
Code Below:
int n,t, cost[MAX][MAX];
string S[MAX];
int dp[(1<<MAX)][MAX];
int calcCost(string X, string Y) {
int res = (int)Y.size();
for(int i = 0;i < X.size();i++) {
int j;
for(j = i; X[j] == Y[j-i] && j < X.size();j++);
if(j == X.size()) {
res = (int)Y.size() - j + i;
break;
}
if(j - i == Y.size()) { res = 0; break; }
}
return res;
}
void calcCosts() {
memset(cost,0,sizeof(cost));
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
if(i != j) {
cost[i][j] = calcCost(S[i], S[j]);
}
}
}
}
int rec(int mask, int last) {
if(mask == (1<<n) - 1) return dp[mask][last] = 0;
if(dp[mask][last]!=-1) return dp[mask][last];
int ans = iinf;
for(int i = 0;i < n;i++) {
if((mask & (1<<i)) == 0)
ans = min(ans, rec(mask | (1<<i), i) + cost[last][i]);
}
return dp[mask][last] = ans;
}
void print(int ans) {
int mask = 0, last = -1;
while(mask != ((1<<n) - 1)) {
for(int i = 0;i < n;i++) {
if((mask & (1<<i)) == 0) {
int toAdd = last == -1 ? (int)S[i].size() : cost[last][i];
if(dp[mask | (1<<i)][i] + toAdd == ans) {
if(last == -1) {
cout<<S[i];
} else {
for(int j = (int)S[i].size() - cost[last][i];j < S[i].size();j++) cout<<S[i][j];
}
last = i;
mask = mask | (1<<i);
ans -= toAdd;
break;
}
}
}
}
}
int main()
{
//cout<<calcCost("CAT", "CATCAT");
cin>>t;
int tc = 1;
while(t--) {
cin>>n;
for(int i = 0;i < n;i++) cin>>S[i];
sort(S,S+n);
calcCosts();
memset(dp,-1,sizeof(dp));
int ans = iinf;
for(int i = 0;i < n;i++) ans = min(ans, rec(1<<i,i) + (int)S[i].size());
cout<<"Scenario #"<<tc<<":"<<endl;
print(ans);
cout<<endl;
tc++;
}
return 0;
}