Java | DP | Bitmask
\nclass Solution {\n    \n    String[][] lookup;\n    \n    String superString(String[] A, int last, int bitmask, String[][] dp){\n        String res = "";   \n
```\nclass Solution {\n    \n    String[][] lookup;\n    \n    String superString(String[] A, int last, int bitmask, String[][] dp){\n        String res = "";   \n        int minLength = Integer.MAX_VALUE/2;\n        if(dp[last][bitmask] != null)\n            return dp[last][bitmask];\n        \n        for(int i=0;i<A.length;i++){\n            if((bitmask&(1<<i)) != 0)\n                continue;\n            String tmp = lookup[last][i]+superString(A, i, bitmask|(1<<i), dp);\n            if(tmp.length() < minLength){\n                minLength = tmp.length();\n                res = tmp;\n            }\n        }\n        return dp[last][bitmask] = res;\n    }\n    \n    public String shortestSuperstring(String[] A) {\n        \n        String[][] dp = new String[A.length][5000];\n        lookup = new String[A.length][A.length];\n        \n        for(int i=0;i<A.length;i++){\n            for(int j=0;j<A.length;j++){\n                if(i == j) continue;\n                int k = 1;\n                int idx = 0;\n                while(k <= A[j].length()){\n                    if(A[i].endsWith(A[j].substring(0, k)))\n                        idx = k;\n                    k++;\n                }\n                lookup[i][j] = A[j].substring(idx, A[j].length());\n            }\n        }\n        \n        String ans = "";\n        int minLength = Integer.MAX_VALUE/2;\n        int bitmask = 0;\n        \n        for(int i=0;i<A.length;i++){\n            String tmp = A[i]+superString(A, i, bitmask|(1<<i), dp);\n            if(tmp.length() < minLength){\n                minLength = tmp.length();\n                ans = tmp;\n            }\n        }\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Bitmask', 'Java']