Easy Recursive Solution in Java Using DP Bitmask
I have used recursive memoized approach as the iterative appraoch would be hard to understand. Similar to TSP Problem.\nThe first call is to a dummy node.\n\n``
I have used recursive memoized approach as the iterative appraoch would be hard to understand. Similar to TSP Problem.\nThe first call is to a dummy node.\n\n```class Solution {\n    private String dp[][];\n    private int n;\n    private int [][] graph;\n    \n    private int overlap(String word1 , String word2)\n    {\n        int word1Len = word1.length();\n        int word2Len = word2.length();\n        for(int i = 0 ; i < word1Len ; i ++)\n        {\n            if(word2.startsWith(word1.substring(i)))\n                return (word2Len - word1Len + i);\n        }\n        return word2Len;\n    }\n    \n    private void computeGraph(String[] words)\n    {\n        for(int i = 0 ; i < n ; i ++)\n            for(int j = 0 ; j < n ; j ++)\n                graph[i][j] = overlap(words[i] , words[j]);\n    }\n    \n    private String getMinString(int mask , int u , String[] words)\n    {\n        if(mask == ((1 << n) - 1))\n            return "";\n        \n        if(dp[mask][u] != null)\n            return dp[mask][u];\n        \n        int minCost = Integer.MAX_VALUE;\n        String minString = "";\n        for(int nextIndex = 0 ; nextIndex < n ; nextIndex ++)\n        {\n            if( (mask & (1 << nextIndex)) == 0)\n            {\n                int cost = (mask == 0) ? words[nextIndex].length() : graph[u][nextIndex];\n                String cur = (mask == 0) ? words[nextIndex] : words[nextIndex].substring(words[nextIndex].length() - graph[u][nextIndex]);\n                \n                String next = getMinString(mask | (1 << nextIndex) , nextIndex , words);\n                cost += next.length();\n                if(cost < minCost)\n                {\n                    minString = cur + next;\n                    minCost = cost;\n                }\n            }\n        }\n        \n        return (dp[mask][u] = minString);\n        \n    }\n    \n    public String shortestSuperstring(String[] words) {\n        n = words.length;\n        dp = new String[(1 << n)][n];\n        \n        graph = new int[n][n];\n        \n        computeGraph(words);\n        \n        return getMinString(0 , 0 , words);\n    }\n}
[]