Java Simple and easy to understand solution, clean code with comments
PLEASE UPVOTE IF YOU LIKE THIS SOLUTION\n\n\n\n\nclass Solution {\n    public String shortestSuperstring(String[] words) {\n        int n = words.length;\n     
**PLEASE UPVOTE IF YOU LIKE THIS SOLUTION**\n\n\n\n```\nclass Solution {\n    public String shortestSuperstring(String[] words) {\n        int n = words.length;\n        \n        int[][] overlaps = createOverlapGraph(words);\n        \n        int maskLen = 1 << n;\n        \n        //dp[mask][i] : maximum overlap of set of words (which is represented by mask), \n        //and ending with words[i]\n        int[][] dp = new int[maskLen][n];\n        \n        //prevWordIndex[mask][i] : Previous word index, after creating the set of words (which is represented by mask),\n        //and ending with words[i]\n        int[][] prevWordIndex = new int[maskLen][n];  \n        \n        \n        calculateMaximumOverlap(words, dp, prevWordIndex, overlaps);\n        \n        //correct order of words, which lead to shortest superstring\n        int[] orders = getCorrectOrder(dp, prevWordIndex);\n        \n        return getShortestSuperString(words, overlaps, orders);\n    }\n    \n    \n    private int[][] createOverlapGraph(String[] words){\n        int n = words.length;\n        int[][] overlaps = new int[n][n];\n        \n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < n; j++){\n                if(i == j) continue;\n                \n                overlaps[i][j] = getOverlap(words[i], words[j]);\n            }\n        }\n        \n        return overlaps;\n    }\n    \n    private int getOverlap(String word, String nextWord){\n        int len = Math.min(word.length(), nextWord.length());\n        \n        for(int i = len; i >= 0; i--){\n            if(word.endsWith(nextWord.substring(0, i))) return i;\n        }\n        \n        return 0;\n    }\n    \n    private void calculateMaximumOverlap(String[] words, int[][] dp, int[][] prevWordIndex, int[][] overlaps){\n        int n = words.length;\n        int maskLen = 1 << n;\n        \n        for(int mask = 1; mask < maskLen; mask++){\n            Arrays.fill(prevWordIndex[mask], -1);\n            \n            for(int maskBitPos = 0; maskBitPos < n; maskBitPos++){\n                    \n                //ignore the zero bit of mask[current set of words]\n                if(((mask >> maskBitPos) & 1) <= 0) continue;\n                \n                //set of word which was selected previously for current mask\n                int prevMask = (mask ^ (1 << maskBitPos));\n                \n                //previous mask is zero, it means, first word we are adding\n                //ignore this, as there will be 0 overlapping\n                if(prevMask == 0) continue;\n                \n                    \n                \n                for(int prevMaskBitPos = 0; prevMaskBitPos < n; prevMaskBitPos++){\n                    \n                    //ignore the zero bit of prevMask[Previous set of words]\n                    if(((prevMask >> prevMaskBitPos) & 1) <= 0) continue;\n                    \n                    //previous set of word overlap, ending with words[prevMaskBitPos]\n                    int prevOverlap = dp[prevMask][prevMaskBitPos];\n                    \n                    //overlap after appending new words[maskBitPos] next to words[prevMaskBitPos]\n                    prevOverlap +=  overlaps[prevMaskBitPos][maskBitPos];\n                    \n                    \n                    \n                    if(prevOverlap >= dp[mask][maskBitPos]){\n                        //replace with maximum overlap\n                        dp[mask][maskBitPos] = prevOverlap;\n                        \n                        prevWordIndex[mask][maskBitPos] = prevMaskBitPos;\n                    }\n                    \n                }\n            }\n        }\n    }\n    \n    private int[] getCorrectOrder(int[][] dp, int[][] prevWordIndex){\n        int rows = dp.length;\n        int cols = dp[0].length;\n        \n        \n        //last word index\n        int lastWordIndex = 0;\n        for(int col = 1; col < dp[0].length; col++){\n            if(dp[rows - 1][col] > dp[rows - 1][lastWordIndex]){\n                lastWordIndex = col;\n            }\n        }\n        \n        int[] orders = new int[cols];\n        int mask = rows - 1;\n        \n        for(int i = cols - 1; i >= 0; i--){\n            orders[i] = lastWordIndex;\n            \n            int prev = prevWordIndex[mask][lastWordIndex];\n            int prevMask = mask ^ (1 << lastWordIndex);\n            \n            mask = prevMask;\n            lastWordIndex = prev;\n        }\n        \n        return orders;\n    }\n    \n    private String getShortestSuperString(String[] words, int[][] overlaps, int[]orders){\n        StringBuilder sb = new StringBuilder(words[orders[0]]);\n        \n        for(int i  = 1; i < orders.length; i++){\n            \n            int overlap = overlaps[orders[i - 1]][orders[i]];\n            \n            String word = words[orders[i]].substring(overlap);\n            sb.append(word);\n        }\n    \n        return sb.toString();\n    }\n}\n```
['Java']