<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 {
    int getCost(string s,string t){
        int m =s.size();
        int n =t.size();
        int i=m-1,j=0;
        for(int i=0;i<m;i++){
            if(m-i+1>n) continue;
            if(s.substr(i,m-i)==t.substr(0,m-i)){
                return n-(m-i);
            }
        }
        return n;
    }
    vector<vector<int>> cost;
    void computeCost(vector<string> &words){
        int n =words.size();
        //cost to append any two words
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) cost[i][i] = 0;
                else{
                    cost[i][j] = getCost(words[i],words[j]);
                }
            }
        }
    }
public:
    string shortestSuperstring(vector<string>& words) {
        //dp(2^12,prev)
        int n =words.size();
        cost.resize(n,vector<int>(n,0));
        int k =1<<n;
        vector<vector<pair<int,string>>> dp(k,vector<pair<int,string>>(n,{1e5,""}));
        computeCost(words);
        for(int mask = 0;mask<k;mask++){
            for(int j=0;j<n;j++){
                //if current word is included
                if(mask&(1<<j)){
                    //preMask is it's state before this word was used
                    int preMask = mask^(1<<j);
                    //if j is the first word
                    if(preMask==0){
                        dp[mask][j] = {words[j].size(),words[j]};
                    }else{
                        int kMin = -1;
                        //now go for all the pre vwords 
                        int minCurrLen = dp[mask][j].first;
                        for(int k=0;k<n;k++){
                            auto pre = dp[preMask][k];
                            int preCost = pre.first;
                            string s = pre.second;
                            if(minCurrLen > cost[k][j]+preCost){
                                kMin=k;
                                minCurrLen = cost[k][j]+preCost;
                            }
                        }
                        if(kMin!=-1){
                            string preStr =  dp[preMask][kMin].second;
                            //add words[j],preStr
                            int overLapLength = words[j].size()-cost[kMin][j];
                            int lenWordsOfJ = words[j].size();
                            preStr+=words[j].substr(overLapLength,cost[kMin][j]);
                            dp[mask][j] = {minCurrLen,preStr};
                        }
                    }
                }
            }
        }
        string ans=  "";
        for(int j=0;j<n;j++){
            string str = dp[k-1][j].second;
            if(ans.size()==0||ans.size()>str.size()) ans=str;
        }
        return ans;
    }
};
444480