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

void printArr(const vector<int> & a){
    for(int i = 0 ; i < a.size() ; i ++) cout<<a[i]<<" ";
    cout<<endl;
}
void printArr(const vector<vector<int>> & a){
    for(int i = 0 ; i < a.size() ; i ++) printArr(a[i]);
}
class Solution {
public:
    string shortestSuperstring(vector<string>& words) {
        if(words.size() == 1) return words[0];
        vector<vector<int>> a(words.size(), vector<int>(words.size(), 240));
        int i, j, k, l;
        for(i = 0 ; i < words.size() ; i ++){
            for(j = 0 ; j < words.size() ; j ++){
                if(i == j) continue;
                int val = 0;
                string s1 = "", s2 = "";
                for(k = 0 ; k < min(words[i].size(), words[j].size()) - 1 ; k ++){
                    s1.push_back(words[i][words[i].size() - 1 - k]);
                    s2.push_back(words[j][k]);
                    reverse(s1.begin(), s1.end());
                    if(s1 == s2){
                        val = s1.size();
                    }
                    reverse(s1.begin(), s1.end());
                }
                a[i][j] = (int) words[j].size() - val;
            }
        }
        //printArr(a);
        int sz = 1 << words.size();
        vector<vector<vector<int>>> dp(words.size(), vector<vector<int>>(words.size(), vector<int>(sz, 240)));
        vector<vector<vector<int>>> prev(words.size(), vector<vector<int>>(words.size(), vector<int>(sz,-1)));
        for(i = 0 ; i < words.size() ; i ++){
            dp[0][i][1 << i] = words[i].size();
        }
        for(i = 1 ; i < dp.size() ; i ++){
            for(j = 0 ; j < words.size() ; j ++){
                for(k = 0 ; k < words.size() ; k ++){
                    if(k == j) continue;
                    for(l = 0 ; l < sz ; l ++){
                        if(((1 << j) & l) == 0){
                            if(dp[i][j][(1<<j)|l] > dp[i-1][k][l] + a[k][j]){
                                dp[i][j][(1<<j)|l] = dp[i-1][k][l] + a[k][j];   
                                prev[i][j][(1<<j)|l] = k;
                            }  
                        }
                    }
                }
            }
        }
        /*cout<<"dp:"<<endl;
        for(i = 0 ; i < dp.size() ; i ++){
            cout<<"i: "<<i<<endl;
            printArr(dp[i]);
        }
        cout<<"prev:"<<endl;
        for(i = 0 ; i < prev.size(); i ++){
            cout<<"i: "<<i<<endl;
            printArr(prev[i]);
        }*/
        int length = 240;
        int x = words.size() - 1, y, z = sz - 1;
        for(i = 0 ; i < words.size() ; i ++){
            if(length > dp.back()[i][sz - 1]){
                length = dp.back()[i][sz - 1];
                y = i;
            }
        }
        //cout<<"length: "<<length<<endl;
        vector<int> path;
        while(y != -1){
            path.push_back(y);
            //cout<<"x: "<<x<<" y: "<<y<<" z: "<<z<<endl;
            int y1 = prev[x][y][z];
            x --;
            int z1 = (z ^ (1 << y));
            y = y1;
            z = z1;
        }
        reverse(path.begin(), path.end());
        //printArr(path);
        string ans = words[path[0]];
        for(i = 1 ; i < path.size() ; i ++){
            int idx = words[path[i]].size() - a[path[i - 1]][path[i]];
            for(j = idx ; j < words[path[i]].size() ; j ++){
                ans.push_back(words[path[i]][j]);
            }
        }
        return ans;
    }
};
50240