<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 sufPre[12][12];
    string dp[13][1<<12];
    int findSufPre(string first, string second){
        for(int i=1;i<first.length();i++){
            if(first[i]==second[0]){
                for(int j=0;j<second.length();j++){
                    if(i+j==first.length()) return j;
                    if(first[i+j]!=second[j])   break;
                }
            }
        }
        return 0;
    }
    void evaluate(vector<string> & words){ //12*12*20*20= 60000
        for(int i=0;i<words.size();i++){
            for(int j=0;j<words.size();j++){
                if(i==j)    {
                    sufPre[i][j]=0;
                    continue;
                }
                sufPre[i][j]=findSufPre(words[i],words[j]);
            }
        }
    }
    string solve(vector<string> & words, int prev, int mask){
        if(mask==0) return "";

        if(dp[prev+1][mask]!=".")return dp[prev+1][mask];

        string ans;
        bool init=false;

        for(int i=0;i<words.size();i++){
            if(mask & (1<<i)){
                int common = prev==-1?0:sufPre[prev][i];
                string toAdd=words[i].substr(common);

                int len=toAdd.length();
                string recurans=solve(words,i,mask&(~(1<<i)));

                if(!init || ans.length()>len+recurans.length())  {
                    init=true;
                    ans=toAdd+recurans;
                }
            }
        }
        return dp[prev+1][mask]=ans;
    }
    string shortestSuperstring(vector<string>& words) {
        //find the prefix and suffix lenght of every left string with every string
        evaluate(words);
        for(int i=0;i<13;i++){
            for(int j=0;j<(1<<12);j++){
                dp[i][j]='.';
            }
        }
        // vector<vector<string>> dp(words.size()+1,vector<string>(1<<words.size(),"."));
        return solve(words,-1,(1<<words.size())-1);
    }
};

136480