[Java] Bitmask DP Solution
dp[i][mask] represents the shortest superstring which ends at i-th word (A[i]), participating words are denoted by mask, for example, mask 0b01011 means partici
* dp[i][mask] represents the shortest superstring which ends at *i-th* word (A[i]), participating words are denoted by mask, for example, mask 0b01011 means participating words are A[0], A[1], A[3]\n* My DP transition function stores the String directly, so I don\'t need to construct the resulting string at the end\n\t* ```String[][] dp = new String[n][1<<n];```\n\n```\nclass Solution {\n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        if (n == 1) {\n            return A[0];\n        }\n        int[][] len = new int[n][n];\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                len[i][j] = getCommonLen(A[i], A[j]);\n                len[j][i] = getCommonLen(A[j], A[i]);\n            }\n        }\n        \n        String[][] dp = new String[n][1<<n];\n        \n        int min = Integer.MAX_VALUE;\n        String minStr = null;\n        for (int i = 1; i < (1<<n); i++) {\n            for (int j = 0; j < n; j++) {\n                if ((i & (1 << j)) == 0) { // A[j] is not in the mask\n                    continue;\n                }\n                if (i == (1 << j)) { // return A[j] if the mask only contains 1 word\n                    dp[j][i] = A[j];\n                    continue;\n                }\n                int state = i ^ (1 << j);\n                int cur = Integer.MAX_VALUE;\n                String curStr = null;\n                for (int x = 0; x < n; x++) {\n                    if (x != j && (i & (1 << x)) > 0 \n                        && dp[x][state].length() + A[j].length() - len[x][j] < cur) {\n                        cur = dp[x][state].length() + A[j].length() - len[x][j];\n                        curStr = dp[x][state] + A[j].substring(len[x][j]);\n                    }\n                }\n                dp[j][i] = curStr;\n                \n\t\t\t\t// get the minimum among all results dp[x][(1<<n)-1]\n                if (i == ((1<<n) - 1)) {\n                    if (min > dp[j][i].length()) {\n                        min = dp[j][i].length();\n                        minStr = dp[j][i];\n                    }\n                }\n            }\n        }\n        return minStr;\n    }\n    \n    private int getCommonLen(String s1, String s2) {\n        int n1 = s1.length();\n        int n2 = s2.length();\n        int n = Math.min(n1, n2);\n        \n        for (int i = n; i >= 0; i--) {\n            if (s1.substring(n1-i, n1).equals(s2.substring(0, i))) {\n                return i;\n            }\n        }\n        \n        return 0;\n    }\n}\n```
[]