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
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:
    # 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
