Given an array A of strings, find any smallest string that contains each string in A as a substring.
We may assume that no string in A is substring of another string in A.
 

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


Example 2:
Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"
 


Note:

1 <= A.length <= 12
1 <= A[i].length <= 20

Difficulty: interview

Starter code:

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        

Solutions:
class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        A = [a for i, a in enumerate(A) if all(a not in b for j, b in enumerate(A) if i != j)]

        def memo(f):
            dic = {}

            def f_alt(*args):
                if args not in dic:
                    dic[args] = f(*args)
                return dic[args]
            return f_alt

        def merge(w1, w2):
            for k in range(len(w2), -1, -1):
                if w1.endswith(w2[:k]):
                    return w1+w2[k:]

        @memo
        def find_short(tup, last):
            if len(tup) == 1:
                return A[tup[0]]
            mtup = tuple(t for t in tup if t != last)
            return min((merge(find_short(mtup, t), A[last]) for t in mtup), key=len)

        tup = tuple(range(len(A)))

        return min((find_short(tup, i) for i in range(len(A))), key=len)


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        N = len(A)
        def Cost(x, y):
            cost = len(y)
            max_similarity = 0
            for i in range(1, min(len(x), len(y))):
                if x[-i:] == y[:i]: max_similarity = i
            return cost - max_similarity
            
        g = [[float('inf')] * N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if i != j:
                    cost = Cost(A[i], A[j])
                    g[i][j] = cost
                else: g[i][j] = len(A[i])
                    
        dp = [[float('inf')] * N for _ in range(1<<N)]
        parent = [[-1] * N for _ in range(1<<N)]
        
        for i in range(N):
            dp[1<<i][i] = len(A[i])
        
        for s in range(1, 1<<N):
            for i in range(N):
                if s & (1<<i):  #valid dp[s][i] check
                    prev = s - (1<<i)
                    for j in range(N):
                        if j != i and prev & (1<<j):
                            cur_cost = dp[prev][j] + g[j][i]
                            if cur_cost < dp[s][i]:
                                dp[s][i] = cur_cost
                                parent[s][i] = j
                                
        min_cost = float('inf')
        ind = -1
        last_row = dp[2**N - 1]
        for i in range(N):
            if last_row[i] < min_cost:
                min_cost = last_row[i]
                ind = i
        
        s = 2**N - 1
        res = A[ind]
        child_ind = ind
        # print(s, ind)
        ind = parent[s][ind]
        s = s - (1<<child_ind)
        while s and ind >= 0:
            cost = g[ind][child_ind]
            pre_len = len(A[ind]) - len(A[child_ind]) + g[ind][child_ind]
            res = A[ind][:pre_len] + res
            child_ind = ind
            # print(s, ind)
            ind = parent[s][ind]
            s = s - (1<<child_ind)
            
        return res
            
                
                
                            
                    
            


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        overlaps = [[0 ]*n for x in range(n)]
        for i, x in enumerate(A):
            for j, y in enumerate(A):
                if i != j:
                    for l in range(min(len(x), len(y)), -1, -1):
                        if x.endswith(y[:l]):
                            overlaps[i][j] = l
                            break
        dp = [[-1]*n for x in range(1<<n)]
        parent = [[None]*n for x in range(1<<n)]
        for mask in range(1, 1<<n):
            for bit in range(n):
                if (mask>>bit) &1:
                    pmask = mask^(1<<bit)
                    if pmask ==0:
                        dp[mask][bit] = 0
                        continue
                    for i in range(n):
                        if (pmask>>i)&1:
                            value = dp[pmask][i] + overlaps[i][bit]
                            if value > dp[mask][bit]:
                                dp[mask][bit] = value
                                parent[mask][bit] = i
        print(dp)
        perm = []
        mask = (1<<n)-1
        i = 0
        for j, val in enumerate(dp[-1]):
            if val > dp[-1][i]:
                i = j
        while i is not None:
            perm.append(i)
            mask, i = mask^(1<<i), parent[mask][i]
        
        perm = perm[::-1]
        '''
        seen = [False] *n
        for x in perm:
            seen[x] = True
        perm.extend([i for i in range(n) if not seen[i]])
        '''
        
        
        ans = [A[perm[0]]]
        for i in range(1, len(perm)):
            overlap = overlaps[perm[i-1]][perm[i]]
            ans.append(A[perm[i]][overlap:])
        return ''.join(ans)
        


# https://zxi.mytechroad.com/blog/searching/leetcode-943-find-the-shortest-superstring/
# 将每个单词看作是一个节点, 两两之间有一条带有权重的有向路径, 权重表示为
# g[i][j]: the cost of appending word[j] after word[i]
# 如将 gcta 放在 catg 后面的 cost 为 3 因为它们有公共子串 g, 所以总长度只需要再增加 3
# 问题转化为了在一个有向图里, 从任意点出发找到经过所有点各一次的最短路径
# dp[s][i]: min cost to visit nodes of s and ends with i (s is a binary string)
# dp[14][2] is the min cost of visit nodes 1, 2, 3 and ends with 2 (14 = 2^1 + 2^2 + 2^3)
# 初始化 dp[2^i][i] = len(A[i]), visit A[i] cost len(A[i])
# dp[s][i] = min(dp[s - 2^i][j] + g[j][i]), 找到所有的没有经过节点 i 的状态, 然后将 i 接在 j 后面
# 结果是 min(dp[2^n - 1][*]), 遍历完了所有的点 (2^n - 1) 的最小 cost
# 用 parent[2^i][i] 数组存储节点 i 的父节点, 以便回溯得到最终的字符串
# O(n^2 * 2^n) time complexity, O(n * 2^n) space complexity
class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        
        def dist(s1, s2):
            ans = 0
            for k in range(min(len(s1), len(s2))):
                if s1[len(s1) - k:] == s2[:k]:
                    ans = len(s2) - k
            return ans
        
        
        n = len(A)
        g = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                g[i][j] = dist(A[i], A[j])
                g[j][i] = dist(A[j], A[i])
        
        parent = [[-1] * n for _ in range(1 << n)]
        dp = [[float('inf')] * n for _ in range(1 << n)]
        for i in range(n):
            dp[1 << i][i] = len(A[i])  # 初始化每个节点是第一个点的情况

        for s in range(1, 1 << n):
            for i in range(n):
                if not (s & (1 << i)):  # 以点 i 作为结尾则状态 s 必须已经访问过 i, 所以 s 的第 i 位是 1
                    continue
                prev = s - (1 << i)  # 找到上一个状态
                for j in range(n):  # 对于所有点, 尝试让它们作为上一个点
                    if dp[prev][j] + g[j][i] < dp[s][i]:
                        dp[s][i] = dp[prev][j] + g[j][i]
                        parent[s][i] = j

        end = dp[-1].index(min(dp[-1]))  # 找到遍历完所有点后的最小 cost 的最终节点
        s = (1 << n) - 1  # 最终的状态
        res = ''
        while s:
            prev = parent[s][end]
            if prev < 0:  # 初始化 parent 为 -1, 小于 0 说明这个节点没有父节点
                res = A[end] + res
            else:
                res = A[end][len(A[end]) - g[prev][end]:] + res
            s &= ~ (1 << end)  # 上一个状态
            end = prev
        return res


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        size = len(A)
        costs = [[0] * size for _ in range(size)]
        for i in range(size):
            for j in range(size):
                if i == j: 
                    costs[i][j] = 0
                    continue
                wi, wj = A[i], A[j]
                si, sj = len(wi), len(wj)
                costs[i][j] = sj
                for k in range(1, min(si, sj) + 1):
                    if wi[-k:] == wj[:k]:
                        costs[i][j] = sj - k
        dp = [[20 * 12] * size for _ in range(1 << size)]
        parent = [[-1] * size for _ in range(1 << size)]
        for i in range(size):
            dp[1 << i][i] = len(A[i])
        for state in range(1, 1 << size):
            for i in range(size):
                if state & (1 << i) == 0: continue
                prev = state - (1 << i)
                for j in range(size):
                    if prev & (1 << j) == 0: continue
                    if dp[state][i] > dp[prev][j] + costs[j][i]:
                        dp[state][i] = dp[prev][j] + costs[j][i]
                        parent[state][i] = j
        minCost = min(dp[-1])
        index = dp[-1].index(minCost)
        res = ''
        state = (1 << size) - 1
        while state:
            prevIndex = parent[state][index]
            if prevIndex < 0: res = A[index] + res
            else:
                cost = costs[prevIndex][index]
                res = A[index][-cost:] + res
            state -= 1 << index
            index = prevIndex
        return res

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def cost(a, b):
            alen, blen = len(a), len(b)
            minlen = min(alen, blen)
            for i in range(minlen - 1,0,-1):
                if a[alen - i:] == b[:i]:
                    return blen - i
            return blen
        n = len(A)
        g = [[-1] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if j == i: continue
                g[i][j] = cost(A[i],A[j])

        dp = [[float('inf')] * n for _ in range(1<<n)]
        parent = [[-1] * n for _ in range(1<<n)]
        anslen = float('inf')
        cur = -1
        ans = ''
        for i in range(n):
            dp[1<<i][i] = len(A[i])
        for s in range(1, 1<<n):
            for j in range(n):
                if (s & (1<<j)) == 0: continue
                ps = s & ~(1 << j)
                for i in range(n):
                    if i == j: continue
                    if dp[s][j] > dp[ps][i] + g[i][j]:
                        dp[s][j] = dp[ps][i] + g[i][j]
                        parent[s][j] = i

        for i in range(n):
            if anslen > dp[(1<<n)-1][i]:
                anslen = dp[(1<<n)-1][i]
                cur = i
        s = (1 << n) - 1
        while s > 0:
            ps = s & ~(1 << cur)
            parent_node = parent[s][cur]
            if ps == 0:
                ans = A[cur] + ans
            else:
                curstr = A[cur]
                ans = curstr[len(curstr) - g[parent_node][cur]:] + ans
            s = ps
            cur = parent_node
        return ans

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def dist(a, b):
            d = len(b)
            for i in range(min(len(a), len(b)), 0, -1):
                if a[-i:] == b[:i]: 
                    d = len(b) - i
                    break
            return d
                
        n = len(A)
        g = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                g[i][j] = dist(A[i], A[j])
                
        dp = [[sys.maxsize]*n for _ in range(1<<n)]
        parent = [[-1]*n for _ in range(1<<n)]
        for i in range(n): dp[1<<i][i] = len(A[i])
        for s in range(1, 1<<n):
            for j in range(n):
                if not s & (1<<j): continue
                ps = s & ~(1<<j)
                for i in range(n):
                    if dp[ps][i] + g[i][j] < dp[s][j]:
                        dp[s][j] = dp[ps][i] + g[i][j]
                        parent[s][j] = i   
                        
        j = dp[-1].index(min(dp[-1]))
        s = (1<<n) - 1
        ans = ''
        while s:
            i = parent[s][j]
            if i < 0: ans = A[j] + ans
            else: ans = A[j][(len(A[j])-g[i][j]):] + ans
            s &= ~(1<<j)
            j = i
        return ans


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def dist(a, b):
            d = len(b)
            for i in range(1, min(len(a), len(b)) + 1):
                if a[-i:] == b[:i]:
                    d = len(b) - i
            return d
        
        n = len(A)
        g = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                g[i][j] = dist(A[i], A[j])
        
        dp = [[sys.maxsize/2]*n for _ in range(1<<n)]
        parent = [[-1]*n for _ in range(1<<n)]
        for i in range(n): dp[1<<i][i] = len(A[i])
        for s in range(1, 1<<n):
            for j in range(n):
                if not s & (1<<j): continue
                ps = s & ~(1<<j)
                for i in range(n):
                    if dp[ps][i] + g[i][j] < dp[s][j]:
                        dp[s][j] = dp[ps][i] + g[i][j]
                        parent[s][j] = i
        
        j = dp[-1].index(min(dp[-1]))
        s = (1<<n) - 1
        ans = ''
        while s:
            i = parent[s][j]
            if i < 0: ans = A[j] + ans
            else:
                ans = A[j][(len(A[j]) - g[i][j]):] + ans
            s &= ~(1<<j)
            j = i
        return ans
        


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        g = [[0]* n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                g[i][j]=len(A[j])
                s=0
                for s in range(min(len(A[i]), len(A[j]))):
                    if A[i][len(A[i])-s:]==A[j][:s]: 
                        g[i][j]=len(A[j])-s
        # print(g)
        dp=[[float('inf')]*(n) for _ in range(2**n)]
        parent=[[-1]*(n) for _ in range(2**n)]
        # print(dp[0])
        for i in range(n):
            dp[2**i][i]=len(A[i])
        for s in range(1, 2**n):
            for i in range(n):
                if s&(2**i)==0: continue
                pre= s &~(1<<i)
                # if pre==0: continue
                for j in range(n):
                    if dp[pre][j]+g[j][i]<dp[s][i]:
                        dp[s][i]=dp[pre][j]+g[j][i]
                        parent[s][i]=j
        # print(dp[-1])
        j = dp[-1].index(min(dp[-1]))
        s=2**n-1
        ans = ''
        while s:
            i= parent[s][j]
            # print(i,j)
            if i<0: ans=A[j]+ans
            else: 
                ans=A[j][(len(A[j])-g[i][j]):]+ans
            s&=~(1<<j)
            j=i
        return ans
        


import numpy as np

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:    
        n = len(A)
        # g[i][j] length of overlap words between A[i] <-> A[j]
        g = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                g[i][j] = len(A[j])
                k = 1
                while k <= min(len(A[i]), len(A[j])):
                    if A[i][len(A[i]) - k:] == A[j][:k]:
                        g[i][j] = len(A[j]) - k
                    k += 1
                    
        # dp[s][i] := min distance to visit nodes (represented as a binary state s)
        # once and only once and the path ends with node i.
        # e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1,
        # the possible paths could be (0, 2, 1), (2, 0, 1).
        dp = [[float('inf')] * n for _ in range(1 << n)]
        parent = [[-1] * n for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = len(A[i])
        
        for s in range(1, 1 << n):
            for j in range(n):
                # s doesn't pass j
                if not (s & (1 << j)):
                    continue
                # parent state, before entering j
                ps = s & ~(1 << j)
                for i in range(n):
                    if dp[ps][i] + g[i][j] < dp[s][j]:
                        dp[s][j] = dp[ps][i] + g[i][j]
                        parent[s][j] = i
        
        j = np.argmin(dp[-1])
        s = (1 << n) - 1
        ans = ''
        while s:
            i = parent[s][j]
            if i < 0:
                ans = A[j] + ans
            else:
                ans = A[j][len(A[j]) - g[i][j]:] + ans
            s &= ~(1 << j)
            j = i
    
            
        return ans

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        # add string t in the end of string s. cost = # of chars can't be merged.
        def mergecost(s, t):
            c = len(t)
            for i in range(1, min(len(s), len(t))):
                if s[len(s) - i:] == t[0:i]:
                    c = len(t) - i
            return c
        
        n = len(A)
        cost = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                cost[i][j] = mergecost(A[i], A[j])
                cost[j][i] = mergecost(A[j], A[i])
        # print('cost = {0}'.format(cost))
        dp = [[float('inf') for _ in range(n)] for _ in range(1 << n)]
        parent = [[-1 for _ in range(n)] for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = len(A[i])
        # print('dp = {0}'.format(dp))
        
        for s in range(1, 1 << n):
            for i in range(n):
                # s doesn't contain index i.
                if not (s & (1 << i)):
                    continue
                # prev -> i
                prev = s - (1 << i)
                for j in range(n):
                    if dp[s][i] > dp[prev][j] + cost[j][i]:
                        dp[s][i] = dp[prev][j] + cost[j][i]
                        parent[s][i] = j
        # print('dp = {0}'.format(dp))
        minCost, end = float('inf'), 0
        for i in range(n):
            if dp[-1][i] < minCost:
                minCost = dp[-1][i]
                end = i
        # print('end = {0}, dp[-1] = {1}'.format(end, dp[-1]))
        # the state that all nodes are visited.
        s = (1 << n) - 1
        res = ''
        while s:
            prev = parent[s][end]
            if prev < 0:
                return A[end] + res
            res = A[end][len(A[end]) - cost[prev][end]:] + res
            s &= ~(1 << end)
            end = prev
        return res


class Solution:
    # https://www.youtube.com/watch?v=u_Wc4jwrp3Q
    # time: O(n^2 * 2 ^ n), space(n * 2 ^ n)
    def shortestSuperstring(self, A: List[str]) -> str:
        # add string t in the end of string s. cost = # of chars can't be merged.
        def mergecost(s, t):
            c = len(t)
            for i in range(1, min(len(s), len(t))):
                if s[len(s) - i:] == t[0:i]:
                    c = len(t) - i
            return c
        
        n = len(A)
        cost = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                cost[i][j] = mergecost(A[i], A[j])
                cost[j][i] = mergecost(A[j], A[i])
        dp = [[float('inf') for _ in range(n)] for _ in range(1 << n)]
        parent = [[-1 for _ in range(n)] for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = len(A[i])
        
        for s in range(1, 1 << n):
            for i in range(n):
                # s doesn't contain index i.
                if not (s & (1 << i)):
                    continue
                # connect i to prev set.
                prev = s - (1 << i)
                for j in range(n):
                    if dp[s][i] > dp[prev][j] + cost[j][i]:
                        dp[s][i] = dp[prev][j] + cost[j][i]
                        parent[s][i] = j
        minCost, end = float('inf'), 0
        for i in range(n):
            if dp[-1][i] < minCost:
                minCost = dp[-1][i]
                end = i
        # the state that all nodes are visited.
        s = (1 << n) - 1
        res = ''
        while s:
            prev = parent[s][end]
            if prev < 0:
                return A[end] + res
            res = A[end][len(A[end]) - cost[prev][end]:] + res
            s &= ~(1 << end)
            end = prev
        return res


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        @lru_cache(None)
        def dp(p, mask):
            if mask == 0:
                return 0, 0
            result = 0
            k = -1
            for j in range(n):
                if not (mask >> j) & 1:
                    continue
                l = g[p].get(j, 0)
                h, x = dp(j,  mask & ~(1 << j))
                h += l
                if h >= result:
                    result = h
                    k = j
            return result, k
        A.insert(0, '*')
        n = len(A)
        g = collections.defaultdict(dict)
        for i in range(n):
            for j in range(n):
                if i == j: continue
                h = min(len(A[i]), len(A[j]))
                for l in range(h - 1, 0, -1):
                    if A[i][-l:] == A[j][:l]:
                        g[i][j] = l
                        break
        mask = (1 << n) - 2
        p = 0
        result = ''
        for i in range(1, n):
            l, x = dp(p, mask)
            result += A[x][g[p].get(x, 0):]
            p = x
            mask = mask & ~(1 << x)
        return result


# 18:31 - 
class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        
        def extra_to_append(w1, w2):
            for i in range(len(w1)):
                if w2.startswith(w1[i:]):
                    return w2[len(w1) - i:]
            return w2
        
        n = len(A)
        extra = [[''] * n for _ in range(n)]
        for (i, j) in itertools.permutations(list(range(n)), 2):
            extra[i][j] = extra_to_append(A[i], A[j])
        
        dp = [[''] * n for _ in range(1 << n)]
        ret = ''
        for mask in range(1, 1 << n):
            for (ci, cw) in enumerate(A):
                if not mask & (1 << ci):
                    continue
                pre_mask = mask & (~(1 << ci))
                if not pre_mask:
                    dp[mask][ci] = cw
                else:
                    for (pi, pw) in enumerate(A):
                        if not pre_mask & (1 << pi):
                            continue
                        if not dp[mask][ci] or len(dp[mask][ci]) > len(dp[pre_mask][pi]) + len(extra[pi][ci]):
                            dp[mask][ci] = dp[pre_mask][pi] + extra[pi][ci]
                if mask == (1 << n) - 1:
                    ret = dp[mask][ci] if not ret or len(ret) > len(dp[mask][ci]) else ret
        
        return ret


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        @lru_cache(None)
        def dp(p, mask):
            if mask == 0:
                return 0, 0
            result = 0
            k = -1
            for j in range(n):
                if not (mask >> j) & 1:
                    continue
                l = g[p].get(j, 0)
                h, x = dp(j,  mask & ~(1 << j))
                h += l
                if h >= result:
                    result = h
                    k = j
            return result, k
        A.insert(0, '*')
        n = len(A)
        g = collections.defaultdict(dict)
        for i in range(n):
            for j in range(n):
                if i == j: continue
                h = min(len(A[i]), len(A[j]))
                for l in range(h - 1, 0, -1):
                    if A[i].endswith(A[j][:l]):
                        g[i][j] = l
                        break
        mask = (1 << n) - 2
        p = 0
        result = ''
        for i in range(1, n):
            l, x = dp(p, mask)
            result += A[x][g[p].get(x, 0):]
            p = x
            mask = mask & ~(1 << x)
        return result


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        @lru_cache(None)
        def dp(i, p, mask):
            if i == n:
                return 0, 0
            result = 0
            k = -1
            for j in range(n):
                if not (mask >> j) & 1:
                    continue
                l = g[p].get(j, 0)
                h, x = dp(i + 1, j,  mask & ~(1 << j))
                h += l
                if h >= result:
                    result = h
                    k = j
            return result, k
        A.insert(0, '*')
        n = len(A)
        g = collections.defaultdict(dict)
        for i in range(n):
            for j in range(n):
                if i == j: continue
                h = min(len(A[i]), len(A[j]))
                for l in range(h - 1, 0, -1):
                    if A[i][-l:] == A[j][:l]:
                        g[i][j] = l
                        break
        mask = (1 << n) - 2
        p = 0
        result = ''
        for i in range(1, n):
            l, x = dp(i, p, mask)
            result += A[x][g[p].get(x, 0):]
            p = x
            mask = mask & ~(1 << x)
        return result


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        # 20*2**12 = 4092*20 = 80000
        N = len(A)
        cost = [
            [0]*N for _ in range(N)
        ]
        for i in range(N):
            for j in range(N):
                # cost of adding A[j] to A[i]
                cost[i][j] = math.inf
                for k in range(len(A[i])):
                    if A[j].startswith(A[i][k:]):
                        cost[i][j] = k+len(A[j])-len(A[i])
                        break
                if cost[i][j] == math.inf:
                    cost[i][j] = len(A[j])
                    
        dp = [[math.inf for _ in range(1<<N)] for i in range(N)]
        for i in range(N):
            dp[i][1<<i] = len(A[i])
        backtrack = [
            [None]*(1<<N) for _ in range(N)
        ]
        for i in range(N):
            backtrack[i][1<<i] = (i, 0)
            
        for i in range(1<<N):
            for j in range(N):
                if i&(1<<j):
                    for k in range(N):
                        if i&(1<<k) and i!=k:
                            if dp[j][i] > dp[k][i^(1<<j)]+cost[k][j]:
                                dp[j][i] = dp[k][i^(1<<j)]+cost[k][j]
                                backtrack[j][i] = (k, i^(1<<j))
        min_cost = math.inf
        min_index = -1
        for i in range(N):
            if min_cost > dp[i][(1<<N)-1]:
                min_cost = dp[i][(1<<N)-1]
                min_index = i
        mask = (1<<N)-1
        order = []
        while mask:
            order.append(min_index)
            min_index, mask = backtrack[min_index][mask]
        order.reverse()
        
        answer = []
        last_i = -1
        for i in order:
            if len(answer) == 0:
                answer.append(A[i])
            else:
                answer.append(A[i][-cost[last_i][i]:])
            last_i = i
        return ''.join(answer)

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        overlaps = [[0] * n for _ in range(n)]
        for i, x in enumerate(A):
            for j, y in enumerate(A):
                for ans in range(min(len(x), len(y)), -1, -1):
                    if x.endswith(y[:ans]):
                        overlaps[i][j] = ans
                        break
        
        maxv = 20 * n + 1
        dp = [[maxv] * n for _ in range(1 << n)]
        parent = [[-1] * n for _ in range(1 << n)]
        
        for i in range(n):
            dp[1 << i][i] = len(A[i])
            
        for s in range(1, 1 << n):
            for i in range(n):
                if not s & (1 << i): continue
                prev = s - (1 << i)
                for j in range(n):
                    if dp[prev][j] + len(A[i]) - overlaps[j][i] < dp[s][i]:
                        dp[s][i] = dp[prev][j] + len(A[i]) - overlaps[j][i]
                        parent[s][i] = j
        
        path = []
        s, i = (1 << n) - 1, 0
        for j in range(1, n):
            if dp[s][j] < dp[s][i]:
                i = j
        path.append(i)
        while len(path) < n:
            j = parent[s][i]
            path.append(j)
            prev = s ^ (1 << i)
            s, i = prev, j
        
        i = path[-1]
        res = [A[i]]
        for j in path[::-1][1:]:
            res.append(A[j][overlaps[i][j]:])
            i = j
        return ''.join(res) 

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        # TSP, DP 
        n = len(A)
        w = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                for k in range(min(len(A[i]), len(A[j])), 0, -1):
                    if A[j].startswith(A[i][-k:]):
                        w[i][j] = k
                        break
        @lru_cache(None)
        def dp(nodes):
            if len(nodes) == 2:return A[nodes[0]]
            end = nodes[-1]
            end_idx = nodes.index(end) 
            # remove the current ending nodes from nodes[:-1]
            nodes_wo_end = nodes[:end_idx]+nodes[end_idx+1:-1]
            # A[end][w[node][end]:] will remove overlap part from the end node.
            return min((dp(nodes_wo_end +(node, ))+A[end][w[node][end]:]
                        for node in nodes_wo_end), key=len)
        return min((dp(tuple(range(n))+(node, )) for node in range(n)), key=len)

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def dist(a, b):
            d = len(b)
            for i in range(min(len(a), len(b)), 0, -1):
                if a[-i:] == b[:i]: return len(b) - i                    
            return d
        
        def build_graph():
            g = [[0]*n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    g[i][j] = dist(A[i], A[j])
            return g
        
        def get_dp():
            dp = [[sys.maxsize]*n for _ in range(1<<n)]
            parent = [[-1]*n for _ in range(1<<n)]
            for i in range(n): dp[1<<i][i] = len(A[i])
            for s in range(1, 1<<n):
                for j in range(n):
                    if not s & (1<<j): continue
                    ps = s & ~(1<<j)
                    for i in range(n):
                        if dp[ps][i] + g[i][j] < dp[s][j]:
                            dp[s][j] = dp[ps][i] + g[i][j]
                            parent[s][j] = i
            return dp, parent
        
        def recover_path():
            j = dp[-1].index(min(dp[-1]))
            s = (1<<n) - 1
            ans = ''
            while s:
                i = parent[s][j]
                if i < 0: ans = A[j] + ans
                else: ans = A[j][(len(A[j])-g[i][j]):] + ans
                s &= ~(1<<j)
                j = i
            return ans
        
        n = len(A)
        g = build_graph()
        dp, parent = get_dp()
        ans = recover_path()
        return ans


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        w = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                for k in range(min(len(A[i]), len(A[j])), 0, -1):
                    if A[j].startswith(A[i][-k:]):
                        w[i][j] = k
                        break
        @lru_cache(None)
        def dp(nodes):
            if len(nodes) == 2:return A[nodes[0]]
            end = nodes[-1]
            end_idx = nodes.index(end) 
            # remove the current ending nodes from nodes[:-1]
            nodes_wo_end = nodes[:end_idx]+nodes[end_idx+1:-1]
            # A[end][w[node][end]:] will remove overlap part from the end node.
            return min((dp(nodes_wo_end +(node, ))+A[end][w[node][end]:]
                        for node in nodes_wo_end), key=len)
        return min((dp(tuple(range(n))+(node, )) for node in range(n)), key=len)        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # n, N = len(A), 1 << len(A)
        # w = [[0] * n for _ in range(n)]
        # for i in range(n):
        #     for j in range(n):
        #         for k in range(min(len(A[i]), len(A[j])), 0, -1):
        #             if A[j].startswith(A[i][-k:]):
        #                 w[i][j] = k
        #                 break
        # f = [[None] * n for _ in range(N)]
        # for i in range(N):
        #     for k in (t for t in range(n) if (1 << t) & i):
        #         i1 = i ^ (1 << k)
        #         f[i][k] = min([f[i1][j] + A[k][w[j][k] :] 
        #                        for j in filter(lambda x: (1 << x) & i1, range(n))],
        #                        key=len, default=A[k])                              
        # return min(filter(None, f[-1]), key=len)        


INF = 1 << 60
class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        
        # calculate overlap
        overlap = [[0] * n for _ in range(n)]
        for i, j in product(range(n), repeat = 2):
            l = min(len(A[i]), len(A[j]))
            overlap[i][j] = max(k for k in range(l + 1) if A[i][len(A[i]) - k:] == A[j][:k])
        
        # TSP
        dp = [[INF] * n for _ in range(1 << n)]
        prev = [[(None, None)] * n for _ in range(1 << n)]
        
        for i, S in enumerate(A):
            dp[1 << i][i] = len(S)
        
        for U, i in product(range(1 << n), range(n)):
            if not U >> i & 1:
                continue
            for ni in range(n):
                if U >> ni & 1:
                    continue
                if dp[U | 1 << ni][ni] > dp[U][i] + len(A[ni]) -  overlap[i][ni]:
                    dp[U | 1 << ni][ni] = dp[U][i] + len(A[ni]) -  overlap[i][ni]
                    prev[U | 1 << ni][ni] = (U, i)
        
        U, i = (1 << n) - 1, min(range(n), key = lambda i : dp[-1][i])
        res = []
        while U is not None:
            res.append(A[i])
            U, i = prev[U][i]
        res.reverse()
        
        ans = ''
        for S in res:
            l = min(len(ans), len(S))
            k = max(k for k in range(l + 1) if ans[len(ans) - k:] == S[:k])
            ans += S[k:]
        return ans

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def dist(a, b):
            for i in range(min(len(a), len(b)), 0, -1):
                if a[-i:] == b[:i]: return len(b) - i
            return len(b)
            
        def get_dist():
            g = [[0]*n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    g[i][j] = dist(A[i], A[j])
            return g
        
        def perform_dp():
            dp = [[sys.maxsize//2]*n for _ in range(1<<n)]
            parent = [[-1]*n for _ in range(1<<n)]
            # init
            for i in range(n): dp[1<<i][i] = len(A[i])
            #
            for s in range(1<<n):
                for j in range(n):
                    if not s & (1<<j): continue
                    ps = s & ~(1<<j)
                    for i in range(n):
                        if dp[ps][i] + g[i][j] < dp[s][j]:
                            dp[s][j] = dp[ps][i] + g[i][j]
                            parent[s][j] = i
            return dp, parent
                            
        def recover_path():
            ans = ''
            j = dp[-1].index(min(dp[-1]))            
            s = (1<<n) - 1
            while s:
                i = parent[s][j]
                if i < 0: ans = A[j] + ans
                else: ans = A[j][-g[i][j]:] + ans
                s &= ~(1<<j)
                j = i
            return ans
        
        n = len(A)
        g = get_dist()
        dp, parent = perform_dp()
        ans = recover_path()
        return ans


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def dist(a, b): # cost to append b to a
            for i in range(min(len(a), len(b)), 0, -1):
                if a[-i:] == b[:i]: return len(b) - i
            return len(b)
            
        def build_graph(): # build cost graph
            graph = [[0]*n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    graph[i][j] = dist(A[i], A[j])
            return graph
        
        def get_dp():
            dp = [[sys.maxsize/2]*n for _ in range(1<<n)]
            parent = [[-1]*n for _ in range(1<<n)]
            for i in range(n): dp[1<<i][i] = len(A[i])
            for s in range(1<<n):
                for j in range(n):
                    if not s & (1<<j): continue
                    ps = s & ~(1<<j)
                    for i in range(n):
                        if dp[ps][i] + g[i][j] < dp[s][j]:
                            dp[s][j] = dp[ps][i] + g[i][j]
                            parent[s][j] = i
            return dp, parent
        
        def recover_path():
            ans = ''
            j = dp[-1].index(min(dp[-1]))
            s = (1<<n) - 1
            while s:
                i = parent[s][j]
                if i < 0: ans = A[j] + ans
                else: ans = A[j][-g[i][j]:] + ans
                s &= ~(1<<j)
                j = i
            return ans
        
        n = len(A)
        g = build_graph()
        dp, parent = get_dp()
        ans = recover_path()
        return ans

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        ''' TSP: DP '''
        n, N = len(A), 1 << len(A)
        
        w = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                for k in range(min(len(A[i]), len(A[j])), 0, -1):
                    if A[j].startswith(A[i][-k:]):
                        w[i][j] = k
                        break
        
        f = [[None] * n for _ in range(N)]
        for i in range(N):
            for k in filter(lambda x: (1 << x) & i, range(n)):
                i1 = i ^ (1 << k)
                f[i][k] = min([f[i1][j] + A[k][w[j][k] :] 
                               for j in filter(lambda x: (1 << x) & i1, range(n))],
                               key=len, default=A[k])                              
        
        return min(filter(None, f[-1]), key=len)

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        def save(w1,w2):
            n = len(w1)
            for i in range(n):
                if w1[i:] == w2[:n-i]:
                    return n-i
            return 0
        
        N = len(A)
        s = [[0] * N for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i != j:
                    s[i][j] = save(A[i],A[j])
        
        end_state = (1<<N) - 1
        
        import functools
        @functools.lru_cache(None)
        def DFS(cur_state,cur_pos):
            if cur_state == end_state:
                return 0,[cur_pos]
            cur_save = -100
            pre_pos = 0
            for pre_pos in range(N):
                if pre_pos == 0 :
                    pre_pos_b = 1
                else:
                    pre_pos_b = pre_pos_b << 1
                if pre_pos_b|cur_state == cur_state:
                    continue
                if cur_save < s[pre_pos][cur_pos] + DFS(cur_state|pre_pos_b,pre_pos)[0]:
                    cur_save = s[pre_pos][cur_pos] + DFS(cur_state|pre_pos_b,pre_pos)[0]
                    path = DFS(cur_state|pre_pos_b,pre_pos)[1] + [cur_pos]
            return cur_save,path
        
        ss = -1
        pp = []
        for last_pos in range(N):
            if not last_pos:
                last_pos_b = 1
            else:
                last_pos_b = last_pos_b << 1
            if ss < DFS(last_pos_b,last_pos)[0]:
                ss,pp = DFS(last_pos_b,last_pos)

        res = A[pp[0]]
        for i in range(1,N):
            res += A[pp[i]][s[pp[i-1]][pp[i]]:]
            
        return res
                


class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        # Building the graph
        graph = [[0] * n for _ in range(n)]
        for i, word1 in enumerate(A):
            for j, word2 in enumerate(A):
                if i == j: continue
                for k in range(min(len(word1), len(word2)))[::-1]:
                    if word1[-k:] == word2[:k]:
                        graph[i][j] = k
                        break
        
        # Recursion. i is a mask to represent the ordering. k is the last node in the ordering.
        memo = {}
        def search(i, k):
            if (i, k) in memo: return memo[i, k]
            # if not (i & (1 << k)): return ''
            if i == (1 << k): return A[k]
            memo[i, k] = ''
            for j in range(n):
                if j != k and i & (1 << j):
                    candidate = search(i ^ (1 << k), j) + A[k][graph[j][k]:]
                    if memo[i, k] == '' or len(candidate) < len(memo[i, k]):
                        memo[i, k] = candidate
            return memo[i, k]
        
        # Finding the best
        res = ''
        for k in range(n):
            candidate = search((1 << n) - 1, k)
            if res == '' or len(candidate) < len(res):
                res = candidate
        return res        

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        self.cost = [[0 for j in range(n)] for i in range(n)]
        for i in range(n):
            for j in range(n):
                w1 = A[i]
                w2 = A[j]
                k = min(len(w1), len(w2))
                while k > 0:
                    if w1[-k:] == w2[:k]:
                        break
                    k -= 1
                
                self.cost[i][j] = k
        
        self.cache = {}
        ans = ''
        for i in range(n):
            candidate = self.dfs(A, i, (1 << n) - 1)
            if ans == '' or len(candidate) < len(ans):
                ans = candidate

        return ans
    
    def dfs(self, A, index, cur):
        if (index, cur) in self.cache:
            return self.cache[(index, cur)]

        if not ((1 << index) & cur):
            return ''
    
        if cur == (1 << index):
            return A[index]
        
        self.cache[(index, cur)] = ''
        for i in range(len(A)):
            if i == index or not ((1 << i) & cur):
                continue
            
            temp = self.dfs(A, i, cur - (1 << index)) + A[index][self.cost[i][index]:]
            if self.cache[(index, cur)] == '' or len(temp) < len(self.cache[(index, cur)]):
                self.cache[(index, cur)] = temp
        
        return self.cache[(index, cur)]



# we can memorize the path while doing dp
# let dp[used][i] = (string length, actual string) represents the bitmask used ends with ith element.

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        common = {}
        for i, s1 in enumerate(A):
            for j in range(i):
                s2 = A[j]
                longest1, longest2 = 0, 0
                for k in range(min(len(s1), len(s2)) + 1):
                    if s1.endswith(s2[:k]):
                        longest1 = k
                    if s2.endswith(s1[: k]):
                        longest2 = k
                common[(i, j)] = longest1
                common[(j, i)] = longest2
        
        end = 1 << n
        dp = [[(float('inf'), '') 
               for i in range(n)] for m in range(end)]
        le, res = float('inf'), ''
        for used in range(end):
            for i, s in enumerate(A):
                if (used >> i) & 1 != 1:
                    continue
                mask = 1 << i
                if used ^ mask == 0:
                    dp[used][i] = (len(A[i]), A[i])
                else:
                    for j, last in enumerate(A):
                        if i == j or (used >> j) & 1 != 1:
                            continue
                        l, pref = dp[used ^ mask][j]
                        cand = pref + A[i][common[(j, i)] :]    
                        if len(cand) < dp[used][i][0]:
                            dp[used][i] = (len(cand), cand)
                if used == end - 1 and dp[used][i][0] < le:
                    le, res = dp[used][i]
        return res


# class Solution:
    
#     def addCost(self, from_word, to_word):
#         n = min(len(from_word), len(to_word))
#         cost = len(to_word)
#         for i in range(n):
#             if from_word[-i-1] == to_word[i]:
#                 cost -= 1
#         return cost 
    
#     def shortestSuperstring(self, A: List[str]) -> str:
#         # initalize 2D adjacency matrix
#         n = len(A)
#         adj_mat = [[0,] * n, ] * n
#         # travers words list, memo the cost by adj_mat
#         for i in range(n):
#             for j in range(n):
#                 if r != c:
#                     from_word, to_word = A[i], A[j]
#                     adj_mat[i][j] = self.addCost(from_word, to_word)
#         # DP memo, the length of start words as the initial values 
#         # dp = [len(w) for w in A] * n 
#         dp = [0, ] * n
#         for i, w in enumerate(A):
#             visited = {w}
#             dp[i] = len(w)
#             while len(visited) < n:
#                 from_w = w
#                 to_w = min(adj_mat[from_w])
                
        
        


class Solution:
    def int2arr(self,x,n):
        arr = []
        x1 = x
        for i in range(n):
            arr.append(x1 % 2)
            x1 = x1 // 2
        return arr
        
    def arr2int(self,arr):
        x=0
        for i in range(len(arr)):
            x+=arr[i]*2**i
        return x
    
    
    
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)
        overlap={}
        for i in range(n):
            for j in range(n):
                short = min(len(A[i]),len(A[j]))
                for k in range(short,-1,-1):
                    if A[i][(len(A[i])-k):(len(A[i]))]==A[j][0:k]:
                        break
                overlap[(i,j)]=k
        #print(self.int2arr(7,5))
        #print(self.arr2int([1, 1, 1, 0, 0]))
        state_order = []
        for i in range(0,n+2):
            state_order.append([])
        for i in range(0,2**(n)):
            arr = self.int2arr(i,n)
            #print(i,arr,sum(arr))
            state_order[sum(arr)].append(i)
        #print(state_order)
        
        m={}
        conn={}
        for i in range(n):
            x = 2**i
            m[x,i]=len(A[i])
            conn[x,i]=A[i]
        for l in range(2,n+1):
            for x in state_order[l]:
                arr = self.int2arr(x,n)
                for end in range(n):
                    if arr[end]==1:
                        m[x,end]=100000
                        x_prev = x-2**end
                        arr_prev = self.int2arr(x_prev,n)
                        for prev in range(n):
                            if arr_prev[prev]==1 and m[x_prev,prev]+len(A[end])-overlap[prev,end]< m[x,end]:
                                m[x,end] = m[x_prev,prev]+len(A[end])-overlap[prev,end]
                                conn[x,end]=conn[x_prev,prev]+A[end][overlap[prev,end]:len(A[end])]
                         
        ans = 100000
        for i in range(n):
            if m[2**n-1,i]<ans:
                ans = m[2**n-1,i]
                ans_str = conn[2**n-1,i]
        
        return ans_str