<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:
    string shortestSuperstring(vector<string>& words) {
        /*
            dp[i][j] = shortest superstring with state i and the last word is words[j]

            ex:
                state: 00011
                dp[state]["ABC"] = dp[prev_state]["FDA"] + dist("FDA", "ABC")
        */
        int n = words.size();
        int total = (1<<n);
        int dist[n][n];
        vector<vector<int>> dp(total, vector<int>(n, INT_MAX/2));
        int parent[total][n];
        memset(dist, 0, sizeof(dist));
        memset(parent, -1, sizeof(parent));

        for(int i=0; i<n; i++){
            dp[1<<i][i] = words[i].size();
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i==j) continue;

                dist[i][j] = cal(words[i], words[j]);
            }
        }
        
        for(int state=1; state<total; state++){
            for(int last=0; last<n; last++){
                if(((state>>last)&1)==0) continue;

                int prev_state = state-(1<<last);
                for(int prev_last=0; prev_last<n; prev_last++){
                    if(((prev_state>>prev_last)&1)==0) continue;

                    if(dp[state][last] > dp[prev_state][prev_last] + dist[prev_last][last]){
                        dp[state][last] = dp[prev_state][prev_last] + dist[prev_last][last];
                        parent[state][last] = prev_last;
                    }
                }
            }
        }

        int min_dist = INT_MAX;
        int final_last = -1;
        int final_state = total-1;
        for(int i=0; i<n; i++){
            if(min_dist>dp[final_state][i]){
                min_dist = dp[final_state][i];
                final_last = i;
            }
        }

        vector<int> res;
        while(final_last!=-1){
            res.push_back(final_last);

            int next_last = parent[final_state][final_last];
            final_state -= (1<<final_last);
            final_last = next_last;
        }
        reverse(res.begin(), res.end());
        string path = words[res[0]];
        for(int i=1; i<res.size(); i++){
            int cur_dist = dist[res[i-1]][res[i]];
            int len = words[res[i]].size();
            path += words[res[i]].substr(len-cur_dist);
        }
        return path;
    }

    int cal(const string& a, const string& b){
        if(a==b) return 0;

        int m = a.size();
        int n = b.size();
        int dp[n];
        memset(dp, 0, sizeof(dp));

        int prev = 0;
        for(int i=1; i<n; i++){
            if(b[prev]==b[i]) dp[i] = ++prev;
            else if(prev>0){
                prev = dp[prev-1];
                i--;
            }
        }

        prev = 0;
        for(int i=0; i<m; i++){
            if(a[i]==b[prev]){
                prev++;
                if(prev==n) return n-prev;
            }
            else if(prev>0){
                prev = dp[prev-1];
                i--;
            }
        }
        return b.size()-prev;
    }
};
19440