Find the Shortest Superstring LeetCode solution in Python

1
class Solution:
2
    def shortestSuperstring(self, words: List[str]) -> str:
3
        n = len(words)
4
        graph = [[0] * n for _ in range(n)]  # graph as adjacency matrix
5

6
        for i in range(n):
7
            for j in range(n):
8
                if i != j:
9
                    for k in range(len(words[j])):
10
                        if words[i].endswith(words[j][:k]):
11
                            graph[i][j] = len(words[j]) - k
12

13
        @cache
14
        def fn(prev, mask):
15
            """Return length of shortest superstring & current choice of word."""
16
            if mask == 0:
17
                return 0, None
18
            vv, kk = inf, None
19
            for k in range(n):
20
                if mask & 1 << k:
21
                    v, _ = fn(k, mask ^ 1 << k)
22
                    offset = len(words[k]) if prev == -1 else graph[prev][k]
23
                    if v + offset < vv:
24
                        vv, kk = v + offset, k
25
            return vv, kk
26

27
        ans = []
28
        prev = -1
29
        mask = (1 << n) - 1
30
        while mask:
31
            _, k = fn(prev, mask)
32
            if ans:
33
                ans.append(words[k][-graph[prev][k] :])
34
            else:
35
                ans.append(words[k])
36
            prev = k
37
            mask ^= 1 << k
38
        return "".join(ans)