Java Bitmask DP
This is a varaint of the travelling salesman problem.\n\n\nclass Solution {\n    \n    public String shortestSuperstring(String[] words) {\n        String[][] t
This is a varaint of the travelling salesman problem.\n\n```\nclass Solution {\n    \n    public String shortestSuperstring(String[] words) {\n        String[][] toAdd = new String[words.length][words.length];\n        String[][] dp = new String[words.length + 1][(1 << (words.length + 1))];\n\n        for (int i = 0; i < words.length; i++) {\n            for (int j = 0; j < words.length; j++) {\n                if (i == j) continue;\n                for (int k = 0; k < words[i].length(); k++) {\n                    String str = words[i].substring(k);\n                    if (words[j].startsWith(str)) {\n                        toAdd[i][j] = words[j].substring(str.length());\n                        break;\n                    }\n                }\n                if (toAdd[i][j] == null) {\n                    toAdd[i][j] = words[j];\n                }\n            }\n        }\n        String ans = "";\n        int minLen = Integer.MAX_VALUE;\n        for (int i = 0; i < words.length; i++) {\n            String str = words[i] + solve(words, toAdd, i, (1 << i), dp);\n            if (str.length() < minLen) {\n                minLen = str.length();\n                ans = str;\n            }\n        }\n        return ans;\n    }\n\n    private String solve(String[] arr, String[][] toAdd, int last, int mask, String[][] dp) {\n        if (mask == (1 << arr.length)-1) {\n            return "";\n        }\n        if (dp[last][mask] != null) {\n            return dp[last][mask];\n        }\n        int minLen = Integer.MAX_VALUE;\n        String ret = "";\n        for (int i = 0; i < arr.length; i++) {\n            if ((mask & (1 << i)) == 0) {\n                String curr = toAdd[last][i] + solve(arr, toAdd, i, mask | (1 << i), dp);\n                if (curr.length() < minLen) {\n                    minLen = curr.length();\n                    ret = curr;\n                }\n            }\n        }\n        return dp[last][mask] = ret;\n    }\n}\n```
[]