Java | the best (Held-Karp ~97%, 17ms) and the worst solution (Greedy backtracking DFS, ~1000ms)
Updated this by adding Solution 2. based on Held-Karp traveling salesman DP algorithm.\n\nSolution 2 - Held-Karp optimized to run for glueable words only (~17ms
Updated this by adding Solution 2. based on Held-Karp traveling salesman DP algorithm.\n\n**Solution 2 - Held-Karp optimized to run for glueable words only (~17ms)**\nThe incrementally improved solution uses Held-Karp-like algorithm (traveling salesman) with bitmask for efficiently iterating subsets of words.\nUnlike in the traveling salesman, my function is max (not min) - but it doesn\'t make a difference (the function maximizes the amount of characters that can be removed by gluing suffixes and prefixes of the word pairs together). Also it needs to run considering all words as the first word, not just one (as the path does not come back to the starting word, like in the traveling salesman). The rest is the same.\nIt also uses the previous idea of removing the non-glueable words from DP (using the remap[] array), but in this case it\'s a smallish improvement for the current set of test cases (20ms->17ms). In addition to the max score array memo[], the next[] array is used to be able to not only find the optimal score, but also reconstruct the optimal solution (order of words). \n```\nclass Solution {\n    int n= -1, k= -1, max= 0;\n    int[] maxOrder, maxcp= null, maxcs= null, remap= null;\n    int[][] lcsps= null;    \n    \n    public String shortestSuperstring(String[] words) {\n        this.n= words.length;\n\t\t// first calculate longest common suffix-prefix for all pairs of strings\n\t\t// also keep max common suffix / prefix per string to easily check for strings \n\t\t// that have no commonalities with other strings either as prefix or suffix (maxcp==0 && maxcs==0)\n\t\tthis.lcsps= new int[n][n];\n        this.maxcp= new int[n];\n        this.maxcs= new int[n];\n        for(int i=0; i<n; i++){\n            for(int j=0; j<n; j++)\n                if(i!=j) {\n                    lcsps[i][j]= lcsp(words[i], words[j]);\n                    maxcp[j]= Math.max(maxcp[j], lcsps[i][j]);\n                    maxcs[i]= Math.max(maxcs[i], lcsps[i][j]);\n                }\n        }\n\n        // reduce the problem if possible, no need to include non-glueable strings in dp\n        this.max= 0;\n        this.maxOrder= new int[n];\n        this.remap= new int[n];\n        this.k= 0;\n        for(int i=n-1, j=0; i>-1; i--){\n            if(maxcp[i]==0 && maxcs[i]==0)\n                maxOrder[n-1-k++]= i;\n            else\n                remap[j++]= i;\n        }\n        // run DP\n        if(k<n) dpts();\n        \n\t\t// build the final string from the optimal order  found\n\t\tStringBuilder sb= new StringBuilder();\n        sb.append(words[maxOrder[0]]);\n        for(int i=1; i<n; i++)\n            sb.append(words[maxOrder[i]].substring(lcsps[maxOrder[i-1]][maxOrder[i]]));\n        return sb.toString();\n    }\n\n    // dynamic programming traveling salesman-like (Held-Karp algorithm)\n    void dpts(){\n        int ndp= n-k;        \n        int[][] memo= new int[ndp][1<<ndp];   // score of optimal order\n        int[][] next= new int[ndp][1<<ndp];   // next word in the optimal order\n        for(int i=0; i<ndp; i++)\n            Arrays.fill(memo[i], -1);\n        max= 0;\n        int first= 0, mask= (1<<ndp)-1; // 1 means available (unvisited)\n        for(int i=0; i<ndp; i++){\n            int score= dpts(i, mask^(1<<i), memo, next);\n            if(score>max){\n                max= score;\n                first= i;\n            }\n        }\n        // recover order\n        maxOrder[0]= remap[first];\n        for(int i=1, j= first, m= mask^(1<<first); i<ndp; i++){\n            j= next[j][m];\n            maxOrder[i]= remap[j];\n            m^= (1<<j);\n        }\n    }    \n\n    int dpts(int i, int mask, int[][] memo, int[][] next){\n        if(mask==0) return 0;\n        int max= memo[i][mask], maxj= -1;\n        if(max!=-1) return max;\n        for(int m=mask; m!=0;){\n            int j= Integer.numberOfTrailingZeros(m);\n            int score= lcsps[remap[i]][remap[j]] + dpts(j, mask^(1<<j), memo, next);\n            if(score>max){\n                max= score;\n                maxj= j;\n            }\n            m^= 1<<j;\n        }\n        next[i][mask]= maxj;\n        return memo[i][mask]= max;\n    }\n\n    \n\t// longest common suffix-prefix for a pair of strings (which is at most len-1 of either string)\n\t// it looks for s1 suffix, s2 prefix - separately invoked for all pairs, in both orders\n    int lcsp(String s1, String s2){\n        int n1= s1.length(), n2= s2.length();\n        for(int i=Math.max(1, n1-n2+1); i<n1; i++)\n            if(s1.endsWith(s2.substring(0,n1-i))) return n1-i;\n        return 0;\n    }    \n}\n```\n**Solution 1 - heuristically optimized brute force ("greedy DFS" across permutations)  (~1000ms, Accepted!)**\nStarted with full brute force, for all permutations.\nThe problem has up to 12 strings which is just above the practical boundary for permutation algos (<=11).\nAfter TLE, added two hacks:\n1. reduced the permutations for certain test cases, by removing strings that cannot be "glued" (reducing length) with any other string -- this is good and correct;\n2. the greedy part:  first processing only permutations for glueable pairs, unless/until the DFS gets stuck (no more such pairs) - then unstucking it by resuming with all remaining permutations -- no proof that this would result in an exact (always correct) solution.\n\n```\nclass Solution {\n    int n= -1,  max= 0;\n    int[] maxOrder= null;\n    int[][] lcsps= null;\n    \n    public String shortestSuperstring(String[] words) {\n        this.n= words.length;\n\t\t// first calculate longest common suffix-prefix for all pairs of strings\n\t\t// also keep max common suffix / prefix per string to easily check for non-glueable strings \n\t\tthis.lcsps= new int[n][n];\n        int[] maxcp= new int[n], maxcs= new int[n];\n        for(int i=0; i<n; i++)\n            for(int j=0; j<n; j++){\n                if(i!=j) lcsps[i][j]= lcsp(words[i], words[j]);\n                maxcp[j]= Math.max(maxcp[j], lcsps[i][j]);\n                maxcs[i]= Math.max(maxcs[i], lcsps[i][j]);\n            }\n        this.max= 0;\n        this.maxOrder= new int[n];\n        boolean[] visited= new boolean[n];\n        int[] order= new int[n];\n        \n        // reduce the problem if possible, no need to include non-glueable strings in dfs\n        int k= 0;\n        for(int i=0; i<n; i++)\n            if(maxcp[i]==0 && maxcs[i]==0){\n                visited[i]= true;\n                order[k++]= i;\n            }\n   \n        // backtracking dfs for optimal permutation search on the remaining unreduced strings (skip if all words are non-glueable)\n        if(k==n)\n            System.arraycopy(order, 0, maxOrder, 0, n);            \n\t\telse\n\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\tif(visited[i]) continue;\n\t\t\t\tvisited[i]= true;\n\t\t\t\torder[k]= i;\n\t\t\t\tdfs(i, k+1, 0, order, visited);\n\t\t\t\tvisited[i]= false;\n\t\t\t}\n\t\t// build the final string from the optimal permutation found\n\t\tStringBuilder sb= new StringBuilder();\n        sb.append(words[maxOrder[0]]);\n        for(int i=1; i<n; i++)\n            sb.append(words[maxOrder[i]].substring(lcsps[maxOrder[i-1]][maxOrder[i]]));\n        return sb.toString();\n    }\n    \n    void dfs(int i, int k, int score, int[] order, boolean[] visited){\n        if(k==n){\n            if(score>max){\n                System.arraycopy(order, 0, maxOrder, 0, n);\n                max= score;\n            }\n            return;            \n        }\n        // // the outer loop is a greedy attempt to prune some permutations and beat TLE:\n        // // 1. visit only glueable pairs to start with\n        // // 2. if we can\'t find any more glueables, brute force the yet unvisited words and hope for the best\n        for(boolean visitedAny= false, glueableOnly= true; !visitedAny; glueableOnly= false)\n            for(int j=0; j<n; j++){\n                if(visited[j] || glueableOnly && lcsps[i][j]==0) continue;\n                visited[j]= visitedAny= true;\n                order[k]= j;\n                dfs(j, k+1, score+lcsps[i][j], order, visited);\n                visited[j]= false;\n            }\n    }\n    \n\t// longest common suffix-prefix for a pair of strings (which is at most len-1 of either string)\n\tint lcsp(String s1, String s2){\n        int n1= s1.length(), n2= s2.length();\n        for(int i=Math.max(1, n1-n2+1); i<n1; i++)\n            if(s1.endsWith(s2.substring(0,n1-i))) return n1-i;\n        return 0;\n    }    \n}
[]