java dp with bitmask o(12 * 2^12 * 12). easy to explain and impl in 20mins. cheers!
\nimport java.util.*;\nimport java.io.*;\n\nclass State {\n    int i;\n    int state;\n    \n    State(int i, int state) {\n        this.i = i;\n        this.st
```\nimport java.util.*;\nimport java.io.*;\n\nclass State {\n    int i;\n    int state;\n    \n    State(int i, int state) {\n        this.i = i;\n        this.state = state;\n    }\n}\n\nclass Solution {\n    private PrintStream out = System.out;\n\n    private int overlap(String a, String b) {\n        int res = 0;\n\n        int n = a.length();\n        for (int i = 1; i < n; ++i) {\n            int j = 0;\n            int k = i;\n            while (k < n && b.charAt(j) == a.charAt(k)) {\n                ++k;\n                ++j;\n            }\n\n            if (k == n) {\n                res = n - i;\n                break;\n            }\n        }\n\n        return res;\n    }\n\n    private int shortestSuperstring(String[] A, int[][] over, int last, int state, State[][] next, Integer[][] dp) {\n        int n = A.length;\n        if (state == ((1 << n) - 1)) {\n            return 0;\n        }\n\n        if (dp[last][state] != null) {\n            return dp[last][state];\n        }\n        \n        int res = Integer.MAX_VALUE;\n        for (int i = 0; i < n; ++i) {\n            if (((state >> i) & 0x1) == 0) {\n                int len = A[i].length() - over[last][i];\n                int ret = shortestSuperstring(A, over, i, state | (1 << i), next, dp) + len;\n                if (ret < res) {\n                    res = ret;\n                    next[last][state] = new State(i, state | (1 << i));\n                }\n            }\n        }\n\n        dp[last][state] = res;\n        return res;\n    }\n\n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n\n        int[][] over = new int[n][n];\n        for (int i = 0; i < n; ++i) {\n            for (int j = i + 1; j < n; ++j) {\n                over[i][j] = overlap(A[i], A[j]);\n                over[j][i] = overlap(A[j], A[i]);\n            }\n        }\n\n        int res = Integer.MAX_VALUE;\n        State[][] next = new State[n][1 << n];\n        Integer[][] dp = new Integer[n][1 << n];\n        int start = -1;\n        for (int i = 0; i < n; ++i) {\n            int ret = shortestSuperstring(A, over, i, 1 << i, next, dp) + A[i].length();\n            if (ret < res) {\n                res = ret;\n                start = i;\n            }\n        }\n        \n        StringBuilder sb = new StringBuilder();\n        int state = 1 << start;\n        sb.append(A[start]);\n        while (state != ((1 << n) - 1)) {  \n            int last = start;\n            State s = next[start][state | (1 << start)];\n            state = s.state;\n            start = s.i;\n            sb.append(A[start].substring(over[last][start]));\n        }\n        return sb.toString();\n    }\n}\n\n```
[]