Java using dp bitmask beats 97%
\nclass Solution {\n    public String shortestSuperstring(String[] words) {  \n        int n = words.length;\n        int[][] cost = buildGraph(words); // runti
```\nclass Solution {\n    public String shortestSuperstring(String[] words) {  \n        int n = words.length;\n        int[][] cost = buildGraph(words); // runtime O(N^2 * L^2)\n        \n        // dp[i][j]: the minimal cost to get to state i with words[j] as the last word\n        int[][] dp = new int[1 << n][n];\n        int[][] precursor = new int[1 << n][n];\n        \n        // Runtime: O(N^2 * 2^N )\n        for (int state = 1; state < (1 << n); state++) {\n            for (int curr = 0; curr < n; curr++) {\n                if ((state & (1 << curr)) == 0) continue; // check if it is a valid state ending with words[curr]\n                int prevState = state ^ (1 << curr); // find its precursor by removing that bit\n                if (prevState == 0) { // if the precursor is empty string\n                    dp[state][curr] = words[curr].length();  // the cost would be the string it selft\n                    precursor[state][curr] = -1;\n                    continue;\n                }\n                int tempMin = Integer.MAX_VALUE;\n                int tempParent = -1;\n                for (int prev = 0; prev < n; prev++) {\n                    if ((prevState & (1 << prev)) == 0) continue;\n                    if (dp[prevState][prev] + cost[prev][curr] < tempMin) {\n                        tempMin = dp[prevState][prev] + cost[prev][curr];\n                        tempParent = prev;\n                    }\n                }\n                dp[state][curr] = tempMin;\n                precursor[state][curr] = tempParent;\n            }\n        }\n        \n        int globalMin = Integer.MAX_VALUE;\n        int last = -1; // the last word to add in the optimal solution\n        for (int i = 0; i < n; i++) {\n            if (globalMin > dp[(1 << n) - 1][i]) {\n                globalMin = dp[(1 << n) - 1][i];\n                last = i;\n            }\n        }\n        \n        // reconstruct the answer to return using the dp table\n        StringBuilder res = new StringBuilder();\n        int state = (1 << n) - 1; // read the dp table backwards starting with the state where all bits are 1\n        while ((state ^ (1 << last)) > 0) {\n            int prev = precursor[state][last];\n            res.insert(0, words[last].substring(words[last].length() - cost[prev][last]));\n            state = state ^ (1 << last);\n            last = prev;\n        }\n        res.insert(0, words[last]);\n        return res.toString();\n    }\n    \n    private int[][] buildGraph(String[] words) {\n        int n = words.length;\n        int[][] g = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                g[i][j] = getCost(words[i], words[j]);\n                g[j][i] = getCost(words[j], words[i]);\n            }\n        }\n        return g;\n    }\n    \n    private int getCost(String s1, String s2) {\n        int i = 0;\n        while (i < s1.length()) {\n            if (s1.charAt(i) == s2.charAt(0)) {\n                int k = i;\n                int p = 0;\n                while (k < s1.length()) {\n                    if (s1.charAt(k) == s2.charAt(p)) {\n                        k++;\n                        p++;\n                    } else {\n                        break;\n                    }\n                }\n                if (k == s1.length()) return s2.length() - p; \n            }\n            i++;\n        }\n        return s2.length();\n    }\n}\n```
[]