NP-hard, use memoization (Oh thank god!)
Here is my solution, time complexity should be O(n^3 * (2^n)), use (1 << n) array to memoize the visited states( i.e. which strings have been included)\n\npubli
Here is my solution, time complexity should be O(n^3 * (2^n)), use (1 << n) array to memoize the visited states( i.e. which strings have been included)\n```\npublic class Solution {\n    private int n;\n    private String[] a;\n    public String shortestSuperstring(String[] A) {\n        n = A.length;\n        a = A;\n        String[] dp = new String[1 << n];\n        return search(dp, (1 << n) - 1);\n    }\n\n    private String search(String[] dp, int bits) {\n        if (dp[bits] != null) return dp[bits];\n        int candLen = Integer.MAX_VALUE;\n        String cand = "";\n        for (int i = 0; i < n; ++i) {\n            if ((bits & (1 << i)) != 0) {\n                int pre = bits ^ (1 << i);\n                String preStr = search(dp, pre);\n                String str = a[i];\n                int n1 = preStr.length(), n2 = str.length();\n                if (n1 + n2 < candLen) {\n                    candLen = n1 + n2;\n                    cand = preStr + str;\n                }\n                int len = Math.min(n1, n2);\n                l: for (int offset = len; offset >= 1; --offset) {\n                    if (n1 + n2 - offset >= candLen) break;\n                    if (str.substring(0, offset).equals(preStr.substring(n1 - offset)))\n                    {\n                        candLen = n1 + n2 - offset;\n                        cand = preStr + str.substring(offset);\n                        break l;\n                    }\n                    if (preStr.substring(0, offset).equals(str.substring(n2 - offset)))\n                    {\n                        candLen = n1 + n2 - offset;\n                        cand = str + preStr.substring(offset);\n                        break l;\n                    }\n                }\n            }\n        }\n        return dp[bits] = cand;\n    }\n}\n```
[]