<p>Given an array of strings <code>words</code>, return <em>the smallest string that contains each string in</em> <code>words</code> <em>as a substring</em>. If there are multiple valid strings of the smallest length, return <strong>any of them</strong>.</p>

<p>You may assume that no string in <code>words</code> is a substring of another string in <code>words</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot;]
<strong>Output:</strong> &quot;alexlovesleetcode&quot;
<strong>Explanation:</strong> All permutations of &quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot; would also be accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;catg&quot;,&quot;ctaagt&quot;,&quot;gcta&quot;,&quot;ttca&quot;,&quot;atgcatc&quot;]
<strong>Output:</strong> &quot;gctaagttcatgcatc&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 12</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 20</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
	<li>All the strings of <code>words</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:

    /*
    Travelling Salesman Problem.
    n = 20;
    Used for mask i.e visited 
    */

    vector<vector<int>> dp, dist, track;
    int visAll, start;

    int solve(int mask, int prevIdx, vector<string>&words){
        if(mask==visAll){return 0;}
        if(prevIdx!=-1 && dp[mask][prevIdx]!=-1){return dp[mask][prevIdx];}

        int ans = INT_MAX;

        for(int i=0; i<words.size(); i++){

            if((mask&(1<<i)) == 0){
                int newAns = solve(mask|(1<<i), i, words);
                if(prevIdx==-1){newAns += words[i].size();}
                else{newAns += dist[prevIdx][i];}

                if(newAns<ans){
                    ans = newAns;
                    if(prevIdx!=-1){track[mask][prevIdx]=i;}
                    else{start=i;}
                }
            }
        }

        if(prevIdx!=-1){dp[mask][prevIdx] = ans;}
        return ans;
    }

    string shortestSuperstring(vector<string>& words) {
        int n = words.size();
        dp.resize(1<<n, vector<int>(n, -1));
        track.resize(1<<n, vector<int>(n, -1));
        dist.resize(n, vector<int>(n)); 
        visAll = (1<<n) - 1;

        // dist[i][j] = trimmed str[j], if str[i] is prefix
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j){dist[i][j] = 0;}
                else {dist[i][j] = findCommon(words[i], words[j]).size();}
            }
        }

        cout<<solve(0, -1, words)<<"\n";
        string res = words[start];

        for(int mask=(1<<start); __builtin_popcount(mask)<n; mask+=(1<<start)){
            res += findCommon(words[start], words[track[mask][start]]);
            start = track[mask][start];
        }

        return res;
    }

//----------------------------------------------------------------------------

    string findCommon(string &str1, string &str2){
        set<string> suffix;
        string tmp = "";
        for(int i=str1.size()-1; i>=0; i--){
            tmp = str1[i] + tmp;
            suffix.insert(tmp);
        }

        tmp = "";

        string ans;
        for(char x : str2){
            tmp.push_back(x);
            if(suffix.find(tmp)!=suffix.end()){
               ans = str2.substr(tmp.size(), str2.size()-tmp.size());
            }
        }

        if(ans.empty()){return str2;}
        return ans;
    }
};
31760