<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:
    vector<int>len;
    vector<vector<int>>overlap;
    vector<vector<int>>dp;
    int n;
    map<pair<int, int>, int>mp;
    int solve(int idx, int mask){
        if(mask == (1 << n) - 1) return 0;
        if(dp[idx][mask] != -1)return dp[idx][mask];
        dp[idx][mask] = INT_MAX;
        for(int i = 0; i < n; i++){
            if((mask&(1 << i)) == 0){
                int temp = len[i] - overlap[idx][i] + solve(i, mask|(1 << i));
                if(temp < dp[idx][mask]){
                    dp[idx][mask] = temp;
                    mp[{idx, mask}] = i;
                }
            }
        }
        return dp[idx][mask];
    }
    string shortestSuperstring(vector<string>& A) {
        n = A.size();
        len.resize(n, 0);
        overlap.resize(n, vector<int>(n, 0));
        dp.resize(n, vector<int>((1 << n) + 1, -1));
        for(int i = 0; i < n; i++){
            len[i] = A[i].size();
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i != j){
                    int m = min(len[i], len[j]);
                    for(int k = m; k >= 0; k--){
                        if(A[i].substr(len[i] - k) == A[j].substr(0, k)){
                            overlap[i][j] = k;
                            break;
                        }
                    }
                }
            }
        }
        int mlen = INT_MAX;
        int idx = 0;
        for(int i = 0; i < n; i++){
            int temp = len[i] + solve(i, (1 << i));
            //cout<<temp<<endl;
            if(temp < mlen){
                mlen = temp;
                idx = i;
            }
        }
        string ans = A[idx];
        int mask = 1 << idx;
        for(int i = 1; i < n; i++){
            int x = idx;
            idx = mp[{idx, mask}];
            ans += A[idx].substr(overlap[x][idx]);
            mask |= (1 << idx); 
        }
        return ans;
    }
};
44080