<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 z_fun(string &s, string &t) {
    int l = 0, r = 0;
    string s1 = t + '%' + s;
    int maxi = 0;
    vector<int> z(s1.size(), 0);
    for (int i = 1; i < s1.size(); i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (z[i] + i < s1.size() && s1[z[i]] == s1[z[i] + i]) {
            z[i]++;
        }
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    for (int i = t.size(); i < s1.size(); i++) {
        if (z[i] + i == s1.size())
            maxi = max(maxi, z[i]);
    }
    return maxi;
}

unordered_map<int, unordered_map<int, string>> dp;
vector<vector<int>> overlap;

string dp_solve(int mask, int last, vector<string>& words) {
    if (dp[mask].find(last) != dp[mask].end()) {
        return dp[mask][last];
    }

    string res = "";
    int n = words.size();
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) {
            string candidate = words[i].substr(overlap[last][i]);
            string next = dp_solve(mask | (1 << i), i, words);
            if (next == "") next = candidate;
            else next = candidate + next;
            if (res == "" || next.size() < res.size()) {
                res = next;
            }
        }
    }

    dp[mask][last] = res;
    return res;
}

void computeOverlap(vector<string>& words) {
    int n = words.size();
    overlap.resize(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                overlap[i][j] = z_fun(words[i], words[j]);
            }
        }
    }
}

string shortestSuperstring(vector<string>& words) {
    int n = words.size();
    computeOverlap(words);
    string ans = "";
    for (int i = 0; i < n; i++) {
        string candidate = words[i] + dp_solve(1 << i, i, words);
        if (ans == "" || candidate.size() < ans.size()) {
            ans = candidate;
        }
    }
    return ans;
}
};
358240