<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:
    // Function to compute the LPS (Longest Prefix Suffix) array for KMP
    void computeLPSArray(const string& pat, vector<int>& lps) {
        int length = 0;
        int i = 1;
        lps[0] = 0; // lps[0] is always 0

        while (i < pat.size()) {
            if (pat[i] == pat[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    int findCommon(string& a, string& b, vector<int>& lps) {
        int m = a.length();
        int n = b.length();

        int i = 0; // index for 'a'
        int j = 0; // index for 'b'

        while (i < m) {
            if (b[j] == a[i]) {
                i++;
                j++;
            }

            if (j == n) {
                return -1; // 'b' is found in 'a'
            } else if (i < m && b[j] != a[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return j; // Longest prefix of 'b' that matches a suffix of 'a'
    }
    string dp(vector<string>& words, int mask, int latest, vector<vector<string>>& mem, vector<vector<int>>& overlap){
        if(mask == 0) return words[latest];
        if(mem[mask][latest] == ""){
            string res = "%";
            for (int i = 0; i < words.size(); ++i) {
                if (mask & (1 << i)) {
                    int o = overlap[i][latest];
                    if(o < 0){
                        string candidate = dp(words, mask ^ (1 << i), latest, mem, overlap);
                        if (res == "%" || res.size() > (candidate.size())) {
                            res = candidate;
                        } 
                    }
                    else{
                        string candidate = dp(words, mask ^ (1 << i), i, mem, overlap);
                        if (res == "%" || res.size() > (words[latest].size() + candidate.size() - o)) {
                            res = words[latest] + candidate.substr(o);
                        } 
                    }
                }
            }
            mem[mask][latest] = res;
        }
        return mem[mask][latest];
    }
    string shortestSuperstring(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> overlap(n, vector<int>(n, -1));
        for(int i = 0; i < n; i++){
            vector<int> lps(words[i].size(), 0);
            computeLPSArray(words[i], lps);
            for(int j = 0; j < n; j++){
                if(i != j){
                    overlap[i][j] = findCommon(words[j], words[i], lps);
                }
                //cout << words[j] << " " << words[i] << " " << overlap[i][j] << endl;
            }
        }
        int mask = ~(~0 << n); 
        vector<vector<string>> mem(mask + 1, vector<string>(n + 1, ""));
        string result = "%";
        for (int i = 0; i < n; ++i) {
            string candidate = dp(words, mask ^ (1 << i), i, mem, overlap);
            //cout << candidate << endl;
            if (result == "%" || result.size() > candidate.size()) {
                result = candidate;
            }
        }
        return result;
    }
};
222720