943. Find the Shortest Superstring
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python []
class Solution:
    def shortestSuperstring(self, words):
        n = len(words)
        overlap = [[0] * n for _ in range(n)]

        def calc_overlap(a, b):
            max_overlap = 0
            for i in range(1, min(len(a), len(b)) + 1):
                if a[-i:] == b[:i]:
                    max_overlap = i
            return max_overlap

        for i in range(n):
            for j in range(n):
                if i != j:
                    overlap[i][j] = calc_overlap(words[i], words[j])

        dp = {}
        def dfs(mask, last):
            if (mask, last) in dp:
                return dp[(mask, last)]
            if mask == (1 << n) - 1:
                return words[last]
            best = None
            for i in range(n):
                if mask & (1 << i) == 0:
                    new_mask = mask | (1 << i)
                    candidate = dfs(new_mask, i)
                    best_candidate = words[last] + candidate[overlap[last][i]:]
                    if best is None or len(best_candidate) < len(best):
                        best = best_candidate
            dp[(mask, last)] = best
            return best

        return min((dfs(1 << i, i) for i in range(n)), key=len)

```
['Python']