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


const int INF = 1e9;
class Solution {
public:
    string shortestSuperstring(vector<string>& words) {

        function<string(string&, string&)> getMergedString = [&](string& s,
                                                                 string& t) {
            int n = s.size(), m = t.size();

            int common = 0;
            for (int index = n - 1, len = 1; index >= 0; index--, len++) {
                len = min(len, m);
                if (s.substr(index, len) == t.substr(0, len)) {
                    common = len;
                }
            }
            return t.substr(common, t.size());
        };

        int n = words.size();
        words.push_back("");

        string dp[n + 1][1ll << (n + 1)];
        string getMergedDp[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                getMergedDp[i][j] = getMergedString(words[i], words[j]);
            }
        }

        function<string(int, int)> TSP = [&](int index, int mask) {
            if (mask == ((1ll << n) - 1)) {
                return (string) "";
            }

            if (dp[index][mask].size()) {
                return dp[index][mask];
            }

            string sss;
            int mn = 1e9;
            for (int i = 0; i < n; i++) {
                if (!((1ll << i) & mask)) {

                    auto ansStr = TSP(i, mask | (1ll << i));
                    string smallStr = getMergedDp[index][i];
                    if (smallStr.size() + ansStr.size() < mn) {
                        mn = smallStr.size() + ansStr.size();
                        sss = smallStr + ansStr;
                    }
                }
            }

            return dp[index][mask] = sss;
        };
        return TSP(n, 0);
    }
};
142640