Solution
C++ []\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& A) {\n        int dp[4096][12] = {0};\n        int failure[12][20] = {0};\n   
```C++ []\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& A) {\n        int dp[4096][12] = {0};\n        int failure[12][20] = {0};\n        int cost[12][12] = {0};\n        int trace_table[4096][12] = {0};\n        const int sz = A.size();\n        const int dp_sz = 1 << sz;\n        \n        for (int i = 0; i < sz; i++) {\n            const int str_sz = A[i].size();\n            \n            failure[i][0] = -1;\n            \n            for (int j = 1, k = -1; j < str_sz; j++) {\n                while (k >= 0 && A[i][k + 1] != A[i][j])\n                    k = failure[i][k];\n                \n                if (A[i][k + 1] == A[i][j]) k++;\n                \n                failure[i][j] = k;\n            }\n        }\n        for (int i = 0; i < sz; i++) {\n            const int i_sz = A[i].size();\n            \n            for (int j = 0; j < sz; j++) {\n                if (i != j) {\n                    const int j_sz = A[j].size();\n                    int h = -1;\n                \n                    for (int k = 0; k < j_sz; k++) {\n                        while (h >= 0 && A[i][h + 1] != A[j][k])\n                            h = failure[i][h];\n                        \n                        if (A[i][h + 1] == A[j][k])\n                            h++;\n                    }\n                    cost[j][i] = i_sz - h - 1;\n                }\n            }\n        }\n        for (int i = 0; i < sz; i++)\n            dp[1 << i][i] = A[i].size();\n        \n        for (int state = 1; state < dp_sz; state++) {\n            for (int t1 = state, b1 = t1 & (-t1); t1 ; t1 ^= b1 , b1 = t1 & (-t1)) {\n                const int state1 = state ^ b1;\n                const int i = __builtin_ctz(b1);\n                const int i_sz = A[i].size();\n                \n                for (int t2 = state1, b2 = t2 & (-t2); t2; t2 ^= b2, b2 = t2 & (-t2)) {    \n                    const int j = __builtin_ctz(b2);\n                    const int tmp = dp[state1][j] + cost[j][i];\n                    \n                    if (!dp[state][i] || tmp < dp[state][i]) {\n                        dp[state][i] = tmp;\n                        trace_table[state][i] = j;\n                    }\n                }\n            }\n        }\n        const auto& last = dp[dp_sz - 1];\n        string res;\n        int i = std::distance(last, std::min_element(last, last + sz));\n        \n        for (int state = dp_sz - 1, j = trace_table[state][i]; state & (state - 1); state ^= (1 << i), i = j, j = trace_table[state][i])\n            res = A[i].substr(A[i].size() - cost[j][i]) + res;\n        \n        return A[i] + res;\n    }\n};\n```\n\n```Python3 []\nclass Solution:\n    def shortestSuperstring(self, words: List[str]) -> str:\n        def getMinSuffix(w1, w2):\n            n = min(len(w1), len(w2))\n            for i in range(n, 0, -1):\n                if w1[-i:] == w2[:i]:\n                    return w2[i:]\n            return w2\n\n        n = len(words)\n        suffix = defaultdict(dict)\n        for i in range(n):\n            for j in range(n):\n                suffix[i][j] = getMinSuffix(words[i], words[j])\n        dp = [[\'\']*n for _ in range(1<<n)]\n        for i in range(1, 1<<n):\n            indexes = [j for j in range(n) if i&(1<<j)]\n            for j in indexes:\n                i2 = i&~(1<<j)\n                strs = [dp[i2][j2]+suffix[j2][j] for j2 in indexes if j2 != j]\n                dp[i][j] = min(strs, key=len) if strs else words[j]\n        return min(dp[-1], key=len)\n```\n\n```Java []\nclass Solution {\n    public String shortestSuperstring(String[] words) {\n        int n = words.length;\n        int[][] mat = new int[n][n];\n        for (int i = 0; i < n; i++) \n            for (int j = i+1; j < n; j++) {\n                mat[i][j] = dist(words[i], words[j]);\n                mat[j][i] = dist(words[j], words[i]);\n            }\n        int[][] dp = new int[1<<n][n];\n        for (int[] row : dp)\n             Arrays.fill(row, Integer.MAX_VALUE / 2);\n\n        int[][] parents = new int[1<<n][n];\n        for (int[] row : parents) \n            Arrays.fill(row, -1);\n\n        for (int i = 0; i < n; i++) \n            dp[1<<i][i] = words[i].length();\n\n        int min = Integer.MAX_VALUE;\n        int cur = 0;\n        for (int s = 1 ; s < (1<<n); s++) {\n            for (int i = 0; i < n; i++) {\n                if ((s & (1 <<i)) == 0) continue;\n                int prevS = s & ~(1 << i);\n                for (int j = 0; j < n; j++) {// i comes from j;\n                    if (dp[prevS][j] + mat[j][i] < dp[s][i]) {\n                        dp[s][i] = dp[prevS][j] + mat[j][i];\n                        parents[s][i] = j;\n                    }\n                }\n                if (s == (1<<n) - 1 && dp[s][i] < min) {\n                    min = dp[s][i];\n                    cur = i;\n                }   \n            } \n        }\n        int s = (1<<n) - 1;\n        String ans = "";\n        while (s > 0 ) {\n            int prev = parents[s][cur];\n            if (prev < 0) ans = words[cur] + ans;\n            else ans = words[cur].substring(words[cur].length() - mat[prev][cur]) + ans;\n            s &= ~(1 << cur);\n            cur = prev;\n        }\n        return ans;\n    }\n    private int dist(String a, String b) {\n        int d = b.length();\n        for (int k = 1; k <= Math.min(a.length(), b.length()); k++) {\n            if (a.endsWith(b.substring(0, k)))\n                d = b.length() - k;\n        }\n        return d;\n    }\n}\n```\n
['C++', 'Java', 'Python3']