(Easy to understand) Python - Recursion + Bitmask cache + overlaps
There are 3 key ideas in this solution.\n\n1. calculate overlap for each string concatenation, since we don\'t need to merge two full string to make a string co
There are 3 key ideas in this solution.\n\n1. calculate overlap for each string concatenation, since we don\'t need to merge two full string to make a string contains both as a substring.\n\tex) "abcd", "cde" -> "abcde" contains both as a substring.\n\n2. We are going to use recursion to build every possible cases. What we need for the recursion are, \n\t1. list of remaining words, \n\t2. the index of the last word we used in the last step (to get the overlap)\n\n3. To keep list of remaining words, there are several ways to do so, but we are going to use bitmask. This will make us easy to cache them, and also save our time to build new list in every recursion call\n\tex) If we use "list" as a parameter of recursion, we should use `new_words = words[:i] + words[i+1:] `\n\t      we can make it with `new_bits = bits - (1<<i)`\nIn our bit mask, `(bits & (1<<i)) == 1 ` means, A[i] is still remaining\n\n4. We can cache partial result, since our recursion function will calculate the optimized result for (remaining_words, last_word_idx). Since we used bitmask for remaining_words, we can use (bitmask: int, last_word_idx: int) tuple as a key\n\tex) If len(A) == 10, and there are 4 remaining words, ended with A[5], This result will be used 5! times. \n\tBecause available prefix should be made with used 6strings, and must be ended with A[5], still we need to make a line with 5 other used strings, # of cases are 5!\n\n\n\n```class Solution(object):\n    def shortestSuperstring(self, A):\n        self.overlaps = [[0 for _ in range(len(A))] for _ in range(len(A))]\n        for i in range(len(A)):\n            for j in range(len(A)):\n                if i == j: continue\n                x, y = A[i], A[j]\n                for count in range(min(len(x), len(y)), -1, -1):\n                    if x.endswith(y[:count]):\n                        self.overlaps[i][j] = count\n                        break\n        self.words = A\n        self.cache = {}\n        wordsbit = (1 << len(A))-1\n        return self.helper(wordsbit, -1)\n    \n    def helper(self, wordsbit, last_word_idx):\n        if not wordsbit:\n            return \'\'\n        key = (wordsbit, last_word_idx)\n        if key in self.cache:\n            return self.cache[key]\n        words = []\n        for i in range(len(self.words)):\n            if (wordsbit>>i) & 1 == 1:\n                words.append((i, self.words[i]))\n        \n        local_res = None\n        for idx, word in words:\n            append_idx = 0\n            if last_word_idx != -1:\n                append_idx = self.overlaps[last_word_idx][idx]\n            new_bit = wordsbit - (1 << idx)\n            child_res = self.helper(new_bit, idx)\n            new_res = word[append_idx:] + child_res\n            if not local_res or len(local_res) > len(new_res):\n                local_res = new_res\n        self.cache[key] = local_res\n        return local_res
['Recursion', 'Python']