Java solution with memorization
```\n/ the used array indicates which word is avaible, used[i] == \'1\', means the word is available...\n * map record the  pairs, means the shortest string we 
```\n/* the used array indicates which word is avaible, used[i] == \'1\', means the word is available...\n * map record the <used array, shortest string> pairs, means the shortest string we can get using the remaining words..\n */\nclass Solution { \n    public String shortestSuperstring(String[] A) {\n        int n = A.length;\n        \n        char[] used = new char[n];\n        Arrays.fill(used, \'1\');\n        Map<String, String> map = new HashMap<>();\n        return findShortestSuperString(A, used, n, map);\n    }\n    \n    private String findShortestSuperString(String[] A, char[] used, int cnt, Map<String, String> map) {\n        //cnt is the number of available words left;\n        int n = A.length;\n        \n        String key = new String(used);\n        if (map.containsKey(key)) {\n            return map.get(key);\n        }\n        \n        //if cnt is 1, then the shortest string can fromed is just that word...\n        if (cnt == 1) {\n            for (int i = 0; i < n; i++) {\n                if (used[i] == \'1\') {\n                    map.put(key, A[i]);\n                }\n            }\n            return map.get(key);\n        } else {\n            //if there are more then one available words left, we just try all possible case, then get the smallest one...\n            String res = null;\n            \n            for (int i = 0; i < n; i++) {\n                if (used[i] == \'0\') continue;\n                used[i] = \'0\';\n                String a = A[i];\n                String b = findShortestSuperString(A, used, cnt - 1, map);\n\t\t\t\t//check if a contains b\n                if (a.indexOf(b) != -1) {\n                    if (res == null || res.length() > a.length()) {\n                        res = a;\n                    }\n                } else if (b.indexOf(a) != -1) { //check if b contains a\n                    if (res == null || res.length() > b.length()) {\n                        res = b;\n                    }\n                } else { \n\t\t\t\t   //check a concatenate with b\n                    int index1 = tailHeadOverlap(a, b);\n                    String s1 = a + b.substring(index1);\n                    if (res == null || res.length() > s1.length()) {\n                        res = s1;\n                    }\n\t\t\t\t\t//check b concatenate with a\n                    int index2 = tailHeadOverlap(b, a);\n                    String s2 = b + a.substring(index2);\n                    if (res == null || res.length() > s2.length()) {\n                        res = s2;\n                    }\n                }\n                used[i] = \'1\';\n            }\n            map.put(key, res);\n        }\n        return map.get(key);\n    }\n    \n    //use the prefix-suffix array of KMP to calculate the number of overlap characters, (prefix of b that is also the suffix of a)\n    private int tailHeadOverlap(String a, String b) {\n        int m = a.length(), n = b.length();\n        if (m > n) { a = a.substring(m - n); }\n        else if (n > m) { b = b.substring(0, m); }\n            \n        String s = b + "#" + a;\n        int k = s.length();\n        int[] preSuf = new int[k];\n        \n        int j = 0;\n        for (int i = 1; i < k; i++) {\n            while (j != 0 && s.charAt(i) != s.charAt(j)) {\n                j = preSuf[j - 1];\n            }\n            if (s.charAt(i) == s.charAt(j)) { j++; }\n            preSuf[i] = j;\n        }\n        return preSuf[k - 1];\n    }\n}
[]