Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

&nbsp;
Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.


Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"


&nbsp;
Constraints:


	1 &lt;= words.length &lt;= 12
	1 &lt;= words[i].length &lt;= 20
	words[i] consists of lowercase English letters.
	All the strings of words are unique.


class Solution:
    def shortestSuperstring(self, A):
        @lru_cache(None)
        def suffix(i,j):
            for k in range(min(len(A[i]),len(A[j])),0,-1):
                if A[j].startswith(A[i][-k:]):
                    return A[j][k:]
            return A[j]
        n = len(A)
        @lru_cache(None)
        def dfs(bitmask, i):
            if bitmask + 1 == 1 << n: return ""
            return min([suffix(i, j)+dfs(bitmask | 1<<j, j) for j in range(n) if not(bitmask & 1<<j)], key = len)
        return min([A[i]+dfs(1<<i,i) for i in range(n)], key = len)
class Solution {
    public String shortestSuperstring(String[] words) {
        int n = words.length;
        int[][] discount = new int[n][n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < words[i].length()&&i!=j; k++){ // build discount map from i->j and j->i
                    if (words[j].startsWith(words[i].substring(k))){
                        discount[i][j]=words[i].length()-k;
                        break;
                    }
                }
            }
        }
        int[][] dp = new int[1<<n][n];
        int[][] path = new int[1<<n][n];
        for (int i = 0; i < 1<<n; i++){ // find the max discount for mask (1<<n)-1 with dp
            for (int j = 0; j < n; j++){
                for (int k = 0; k < n && (i&1<<j)>0; k++){
                    if ((i&1<<k)==0 && dp[i][j]+discount[j][k]>=dp[i|1<<k][k]){
                        dp[i|1<<k][k]=dp[i][j]+discount[j][k];
                        path[i|1<<k][k]=j;
                    }
                }
            }
        }
        int m = (1<<n)-1, idx = n; // build the path from end to start
        int end=IntStream.range(0,n).reduce((a,b)->dp[(1<<n)-1][a]>dp[(1<<n)-1][b]?a:b).getAsInt();
        String[] ans = new String[n];
        while(m>0){
            ans[--idx]=words[end].substring((m&(m-1))==0?0:discount[path[m][end]][end]);
            m^=1<<end;
            end=path[m|1<<end][end];
        }
        return String.join("",ans);
    }
}
vector<vector<int> > dp,pre,par;

bool startWith(string s, string t)
{
// returns true if string s starts with string t
    int i;
    for(i=0; i<s.length()&&i<t.length(); i++)
    {
        if(s[i]==t[i])
            continue;
        else
            return false;
    }
    if(i==t.length())
        return true;
    else
        return false;
}

int calc(string A, string B)
{
 // calculate the number of extra characters required to be appended to A
 // if A is followed by B
 // for eg. calc("abcd","cdef") = 2
 
    int a=A.length(),b=B.length();
    for(int i=0; i<a; i++)
    {
        if(a-i<=b&&startWith(B,A.substr(i)))
        {
            return b-(a-i); 
        }
    }
    return b;
}

int finalMask,n;

int helper(int mask, int last)
{
 // returns the minimum length of string required if last string appended was A[last] 
 // the sets bit in mask represents the strings that were already appended to the final string
 
    if(mask==finalMask)  // all strings are appended in final string
        return 0;

    if(dp[mask][last]!=-1) // memoization
        return dp[mask][last];
        
    int mn=INT_MAX;
    int p;
    for(int i=0; i<n; i++)
    {
        if(mask&(1<<i))
            continue;
        int cost=pre[last][i]+helper(mask|(1<<i),i);  // extra characters need to be appended
        if(cost<mn)
        {
            mn=cost;
            p=i;
        }
    }
    par[mask][last]=p;  // store parent, so that it is easy to traceback and find the final result
    return dp[mask][last]=mn; // store result in DP table
}



class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
    n=A.size();
    pre.assign(n,vector<int>(n));  // for pre-computing calc(a,b) for all pairs of strings
    par.assign(1<<n,vector<int>(n,-1));    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(j==i)
                continue;
            pre[i][j]=calc(A[i],A[j]);
        }
    }
    finalMask=(1<<n)-1;  
    dp.assign(1<<n,vector<int>(n,-1));
    int len=INT_MAX;  // len will contain minimum length of required string
    int ind;
    for(int i=0; i<n; i++)
    {
        int prev=len;
        len=min(len, (int)A[i].length()+helper(1<<i,i));
        if(len!=prev)
        {
            ind=i;
        }
    }

 // Now traceback to find the final answer
    string ans=A[ind];
    int msk=1<<ind;
    int prev_ind=ind;
    ind=par[msk][ind];
    while(ind!=-1)
    {
        len=pre[prev_ind][ind];
        int alen=A[ind].length();
        ans+=A[ind].substr(alen-len,len);            
        msk=msk^(1<<ind);
        prev_ind=ind;
        ind=par[msk][ind];  
    }
        return ans;
    }
};
var shortestSuperstring = function(words) {
    let N = words.length, suffixes = new Map(),
        edges = Array.from({length: N}, () => new Uint8Array(N))

    // Build the edge graph
    for (let i = 0, word = words; i < N; i++) {
        let word = words[i]
        for (let k = 1; k < word.length; k++) {
            let sub = word.slice(k)
            if (suffixes.has(sub)) suffixes.get(sub).push(i)
            else suffixes.set(sub, [i])
        }
    }
    for (let j = 0; j < N; j++) {
        let word = words[j]
        for (let k = 1; k < word.length; k++) {
            let sub = word.slice(0,k)
            if (suffixes.has(sub))
                for (let i of suffixes.get(sub))
                    edges[i][j] = Math.max(edges[i][j], k)
        }
    }

    // Initialize DP array
    let M = N - 1,
        dp = Array.from({length: M}, () => new Uint16Array(1 << M))

    // Helper function to find the best value for dp[curr][currSet]
    // Store the previous node with bit manipulation for backtracking
    const solve = (curr, currSet) => {
        let prevSet = currSet - (1 << curr), bestOverlap = 0, bestPrev
        if (!prevSet) return (edges[M][curr] << 4) + M
        for (let prev = 0; prev < M; prev++)
            if (prevSet & 1 << prev) {
                let overlap = edges[prev][curr] + (dp[prev][prevSet] >> 4)
                if (overlap >= bestOverlap)
                    bestOverlap = overlap, bestPrev = prev
            }
        return (bestOverlap << 4) + bestPrev
    }

    // Build DP using solve
    for (let currSet = 1; currSet < 1 << M; currSet++)
        for (let curr = 0; curr < N; curr++)
            if (currSet & 1 << curr)
                dp[curr][currSet] = solve(curr, currSet)

    // Join the ends at index M
    let curr = solve(M, (1 << N) - 1) & (1 << 4) - 1

    // Build the circle by backtracking path info from dp
    // and find the best place to cut the circle
    let path = [curr], currSet = (1 << M) - 1,
        bestStart = 0, lowOverlap = edges[curr][M], prev
    while (curr !== M) {
        prev = dp[curr][currSet] & (1 << 4) - 1, currSet -= 1 << curr
        let overlap = edges[prev][curr]
        if (overlap < lowOverlap)
            lowOverlap = overlap, bestStart = N - path.length
        curr = prev, path.unshift(curr)
    }

    // Build and return ans by cutting the circle at bestStart
    let ans = []
    for (let i = bestStart; i < bestStart + M; i++) {
        let curr = path[i%N], next = path[(i+1)%N], word = words[curr]
        ans.push(word.slice(0, word.length - edges[curr][next]))
    }
    ans.push(words[path[(bestStart+M)%N]])
    return ans.join("")
};
Find the Shortest Superstring