<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:

    int D(string x, string y){
        int k = 0 ;
        int n  = x.size();


        while(k != -1){
            k =  x.find(y[0], k);
            if(k == -1) break;
            if(x.substr(k) == y.substr(0, n-k)){
                return y.size() - (n - k);
            }
            k++;
        }
        return y.size();
    }


    string shortestSuperstring(vector<string>& a) {
        
        
        int n = a.size();
        // dp[mask][i] : min superstring made by string
        int ALL_VISITED = (1 <<  n) - 1;
        vector<vector<int>> dp(1<< n, vector<int>(n, INT_MAX - 1000));
        for(int i = 0 ; i <  n; i++){
            dp[1 << i][i] = a[i].size(); 
        }
        for(int mask = 1 ; mask < 1 << n; mask++ ){
            for(int i = 0 ; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(!(mask & (1 << i)) &&(mask & (1 << j))){
                    	 // cout << D(a[j], a[i]) << " " <<dp[mask][j] << endl;
                         dp[mask | 1 << i][i] =  min(dp[mask | 1 << i][i], dp[mask][j] + D(a[j], a[i]));
                    }
                }
              }
        }

        // for(int i = 1 ;i <= ALL_VISITED ; i++){
        // 	cout << i << "  "; 
        // 	for(int j = 0 ; j < n ; j++){
        		
        // 		if(dp[i][j] < 1000){
        // 			cout << dp[i][j] << " ";
        // 		}
        // 		else{
        // 			cout << "-" << " ";
        // 		}
        // 	}
        		
        // 		cout << endl;
        // }


        vector<int> order;
        int mask  = ALL_VISITED;
        int last_index = -1;
        while(mask){

            int index = -1;
            int best = INT_MAX;
        
            for(int i = 0 ; i <  n; i++){
            	int curr = dp[mask][i] + (last_index != -1 ? D(a[i], a[last_index])  : 0);
                if( curr < best){
                    best =  curr;
                    index = i;
                }
            }
            


            last_index = index;

            order.push_back(index);
            mask ^= 1 << index;
        }
       	reverse(order.begin(), order.end());
       	string res = a[order[0]];
       	for(int  i =  1; i  < order.size(); i++){
       		int dis = D(a[order[i-1]], a[order[i]]);
       		res += a[order[i]].substr(a[order[i]].size() - dis);
       	}
       	return res;
         
    }
};
68720