<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<vector<string>> findCost(vector<string> &words)
    {
        int n = words.size();
        vector<vector<string>> ans(n+1, vector<string> (n+1));
        for ( int i = 0; i < n; i++)
        {
            for ( int j = 0; j < n; j++)
            {
                if ( i!=j )
                {
                    string a = words[i], b = words[j];
                    for ( int k = 0; k < a.length(); k++)
                        if( b.rfind(a.substr(k),0) != string::npos ) 
                        {
                            ans[i][j] = b.substr(a.length()-k);
                            break;
                        }
                    if ( ans[i][j] == "" ) ans[i][j] = b;
                }
            }
        }
        return ans;
    }

    string Solve(int pre, int bitmask, vector<string> &words, vector<vector<string>> &cost, vector<vector<string>> &mem)
    {
        if ( bitmask == 0 ) return "";
        if ( mem[pre][bitmask] != "" ) return mem[pre][bitmask];
        string res = "";
        int lengRes = INT_MAX;
        for ( int k = 0; k < words.size(); k++ )
        {
            if ( (1<<k)&bitmask )
            {
                string tmp = cost[pre][k] + Solve(k, bitmask^(1<<k), words, cost, mem);
                if ( tmp.length() < lengRes )
                {
                    res = tmp;
                    lengRes = tmp.length();
                }
            }
        }
        return mem[pre][bitmask] = res;
    }

    string shortestSuperstring(vector<string>& words) 
    {
        int n = words.size();
        vector<vector<string>> cost(n+1, vector<string> (n+1));
        cost = findCost(words);
        vector<vector<string>> mem(n+1, vector<string> ((1<<(n+1)), "") );
        string ans = "";
        int lengAns = INT_MAX;
        for ( int i = 0; i < n; i++ )
        {
            string tmp = words[i] + Solve(i, ((1<<n)-1)^(1<<i), words, cost, mem);
            if ( tmp.length() <  lengAns )
            {
                ans = tmp;
                lengAns = tmp.length();
            }
        }
        return ans;
    }
};
272000