[Java] Recursion + Memoization + Optimal Path Reconstruction
Top voted solutions are mostly iterative. This is an example of how you can construct an optimal path with a recursive dp solution. In the path reconstruction f
Top voted solutions are mostly iterative. This is an example of how you can construct an optimal path with a recursive dp solution. In the path reconstruction function we can begin from the same start state and at each step follow (the already precalculated) best move - in this case the minimum final string length.\n\n```java\n    static int n;\n    static int[][] g;\n    static int[][] dp;\n    static String[] w;\n\n    public String shortestSuperstring(String[] words) {\n        w = words;\n        n = words.length;\n        g = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                g[i][j] = getCost(words[i], words[j]);\n                g[j][i] = getCost(words[j], words[i]);\n            }\n        }\n        dp = new int[n][1 << n];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n        dfs(0, 0);\n        return getString(0, 0);\n    }\n\n    private static int getCost(String a, String b) {\n        for (int i = 1; i < a.length(); i++) {\n            if (b.startsWith(a.substring(i))) {\n                return b.length() - a.length() + i;\n            }\n        }\n        return b.length();\n    }\n\n    private static String getString(int u, int mask) {\n        if (mask == (1 << n) - 1) {\n            return "";\n        }\n        int best = (int) 1e9;\n        int bestIdx = -1;\n        for (int v = 0; v < n; v++) {\n            if ((mask & (1 << v)) == 0) {\n                final int cost = mask == 0 ? w[v].length() : g[u][v];\n                if (best > cost + dp[v][mask | (1 << v)]) {\n                    best = cost + dp[v][mask | (1 << v)];\n                    bestIdx = v;\n                }\n            }\n        }\n        final String curr = mask == 0 ? w[bestIdx] : w[bestIdx].substring(w[bestIdx].length() - g[u][bestIdx]);\n        return curr + getString(bestIdx, mask | (1 << bestIdx));\n    }\n\n    private static int dfs(int u, int mask) {\n        if (mask == (1 << n) - 1) {\n            return 0;\n        }\n        if (dp[u][mask] != -1) {\n            return dp[u][mask];\n        }\n        int res = (int) 1e9;\n        for (int v = 0; v < n; v++) {\n            if ((mask & (1 << v)) == 0) {\n                final int cost = mask == 0 ? w[v].length() : g[u][v];\n                res = Math.min(res, cost + dfs(v, mask | (1 << v)));\n            }\n        }\n        return dp[u][mask] = res;\n    }\n```
[]