<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>> len_match;
    // map<pair<int,int>,string> dp;
    string match(string& s,string& t)
    {
        string ans="";
        for(int i=0;i<s.size();i++){
            string x=s.substr(i);
            if(t.size()>=(s.size()-i)){
                string y=t.substr(0,s.size()-i);
                if(y==x) if(y.size()>ans.size()) ans=y;
            }
        }
        int xx=ans.size();
        return t.substr(xx);
    }
    string solve(int i,int vis,vector<string>& words,vector<vector<string>>& dp){
        int n=words.size(),cnt=0;
        // vis[i]=1;
        // if(dp)

        vis=(vis|(1<<i));
        for(int j=0;j<n;j++) if(vis&(1<<j)) cnt++;
        if(cnt==n) return "";
        if(dp[i][vis]!="0") return dp[i][vis];
        string ans="";
        for(int j=0;j<n;j++)
        {
            if(!(vis&(1<<j))){
                string x= len_match[i][j] + solve(j,vis,words,dp);
                if(cnt==1) {
                    // x=x+words[i];
                    x=words[i]+x;
                }
                if(ans=="" || (ans.size() > x.size())) ans=x;
            }
        }
        return dp[i][vis]=ans;
    }
    string shortestSuperstring(vector<string>& words) {
        int n=words.size();
        if(n==1) return words[0];
        len_match.resize(n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                len_match[i].push_back(match(words[i],words[j]));
            }
        }
        // for(auto x: len_match) {
        //     for(auto y: x) cout<<y<<" ";
        //     cout<<endl;
        // }
        // vector<int> vis(n,0);
        int vis=0;
        // return "";
        // return solve(0,vis,words);
        string res="";
        int x=pow(2,n+1);
            vector<vector<string>> dp(n,vector<string>(x,"0"));

        for(int i=0;i<n;i++)
        {
            string x= solve(i,vis,words,dp);
            if(res=="" || res.size()>x.size()) res=x;
        }

        return res;

    }
};
302800