# 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
import collections


class Solution(object):
    def shortestSuperstring(self, A):
        """
        :type A: List[str]
        :rtype: str
        """
        mp, ms, ps = collections.defaultdict(list), collections.defaultdict(list), set()
        res, dup, used = "", collections.defaultdict(list), [False] * len(A)

        for k, v in enumerate(A):
            for i in xrange(1, len(v) + 1):
                pre, suff = v[:i], v[len(v) - i:]
                mp[pre].append(k)
                ps.add(pre)
                ms[suff].append(k)
                if suff in ps:
                    for idx in mp[suff]:
                        if idx != k:
                            dup[suff].append((k, idx))

        for key in sorted(dup.keys(), key=len, reverse=True):
            for pair in dup[key]:
                if not used[pair[0]] and not used[pair[1]]:
                    idx = A[pair[0]].find(key)
                    res += A[pair[0]][:idx] + A[pair[1]]
                    used[pair[0]], used[pair[1]] = True, True
                elif not used[pair[1]]:
                    res += A[pair[1]][len(key):]

        for k, v in enumerate(A):
            if not used[k]:
                res += v

        return res


if __name__ == '__main__':
    print Solution().shortestSuperstring(["catg", "ctaagt", "gcta", "ttca", "atgcatc"])
    print Solution().shortestSuperstring(["alex", "loves", "leetcode"])
