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

#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
    vector<vector<string>> req;

    string merge(string &a, string &b) { // a is followed by b (ab)
        int n = a.size(), m = b.size(), len = 1, idx = 0;
        while (len <= min(n, m)) {
            if (a.substr(n - len) == b.substr(0, len)) {
                idx = len;
            }
            len++;
        }
        string res = b.substr(idx);
        return res;
    }

    string rec(vector<string> &words, int prev, int mask, int n, vector<vector<string>> &dp) {
        if (mask == 0) return "";

        if (prev != -1 && dp[prev][mask] != "") return dp[prev][mask];
        string res;
        int mini = INT_MAX;

        if (prev == -1) {
            for (int i = 0; i < n; i++) {
                if ((mask >> i) & 1) {
                    int newmask = mask ^ (1 << i);
                    string tmp = words[i] + rec(words, i, newmask, n, dp);

                    if (tmp.size() < mini) {
                        mini = tmp.size();
                        res = tmp;
                    }
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                if ((mask >> i) & 1) {
                    int newmask = mask ^ (1 << i);
                    string tmp = req[prev][i] + rec(words, i, newmask, n, dp);

                    if (tmp.size() < mini) {
                        mini = tmp.size();
                        res = tmp;
                    }
                }
            }
        }

        if (prev != -1) dp[prev][mask] = res;
        return res;
    }

public:
    string shortestSuperstring(vector<string>& words) {
        int n = words.size();
        req.resize(n, vector<string>(n, ""));
        vector<vector<string>> dp(n, vector<string>(1 << n, ""));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                req[i][j] = merge(words[i], words[j]);
            }
        }

        return rec(words, -1, (1 << n) - 1, n, dp);
    }
};

247360