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

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Dynamic programming

Data structures

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:
					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
		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
			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]
		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)


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:
					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]))
		s = (1 << n) - 1
		res = ''
		while s:
			prev = parent[s][end]
			if prev < 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:
		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
		dp = [[float('inf')] * n for _ in range(2 ** n)]
		parent = [[-1] * n for _ in range(2 ** n)]
		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)
				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
		j = dp[-1].index(min(dp[-1]))
		s = 2 ** 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


import numpy as np

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])
				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 = [[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):
				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 = 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:

		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):
				if not s & 1 << i:
					continue
				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
		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


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:
		N = len(A)
		cost = [[0] * N for _ in range(N)]
		for i in range(N):
			for j in range(N):
				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:
		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)
			nodes_wo_end = nodes[:end_idx] + nodes[end_idx + 1:-1]
			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)


INF = 1 << 60

class Solution:

	def shortestSuperstring(self, A: List[str]) -> str:
		n = len(A)
		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]))
		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 build_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:
		(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)
		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
		memo = {}

		def search(i, k):
			if (i, k) in memo:
				return memo[i, k]
			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]
		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]


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 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
		state_order = []
		for i in range(0, n + 2):
			state_order.append([])
		for i in range(0, 2 ** n):
			arr = self.int2arr(i, n)
			state_order[sum(arr)].append(i)
		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