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

    map<pair<int,int>, string> dp;

    map<pair<int,int>, int> mp;

    int getMatch(vector<string> &v, int x, int y) {
        int ans=0;
        for(int i=v[x].size()-1;i>=0;i--) {
            bool f=true;
            if(v[y].size()-1<i) continue;
            for(int j=v[x].size()-i,k=0;j<v[x].size();j++,k++) {
                if(v[x][j]!=v[y][k]) {
                    f=false;
                    break;
                }
            }
            if(f) return i;
        }
        return 0;
    }

    string deepee(vector<string> &v, int bt, int p) {
        if(bt==0) return v[p];
        if(dp[make_pair(bt,p)].size()) return dp[make_pair(bt,p)];
        int mn=INT_MAX;
        string ans="";
        int x=1;
        for(int i=0;i<v.size();i++) {
            if(bt&x) {
                string curr=deepee(v,bt^x,i);
                if(mn>curr.size()+v[p].size()-mp[make_pair(p,i)]) {
                    ans=""; 
                    mn=curr.size()+v[p].size()-mp[make_pair(p,i)];
                    for(int j=0;j<v[p].size()-mp[make_pair(p,i)];j++) {
                        ans.push_back(v[p][j]);
                    }
                    ans+=curr;
                }
            }
            x*=2;
        }
        dp[make_pair(bt,p)]=ans;
        // if(v.size()==6) cout << bt << " " << p << " " << ans << endl;
        return ans;
    }

    string shortestSuperstring(vector<string>& words) {
        dp.clear();
        words.push_back("");
        int x=1,bt=0;
        for(int i=0;i<words.size();i++) {
            bt|=x;
            x=2*x;
        }
        for(int i=0;i<words.size();i++) {
            for(int j=i+1;j<words.size();j++) {
                mp[make_pair(i,j)]=getMatch(words,i,j);
                // cout << i << " " << j << " " << mp[make_pair(i,j)] << endl;
                mp[make_pair(j,i)]=getMatch(words,j,i);
                // cout << j << " " << i << " " << mp[make_pair(j,i)] << endl;
            }
        }
        return deepee(words,bt^(x/2),words.size()-1);
    }
};
130320