Leetcode: 943. Find the Shortest Superstring

• Pattern: Problem's constraints allow time complexity of \(O(2^n \times X)\).
• Pattern: Problem's constraints play big role on the solution. One word can only cover a part of any other word in the dictionary. Therefore, a word always increase the number of covered words in 1 when picking it.
• Pattern: Optimization problem to find the smallest/longest X that respect condition Y.

Suppose that we have \(f(i, S)\) that computes the smallest string starting with \(words[i]\) and covering all words not in \(S\). We can solve the problem by finding \(i\) which \(f(i, S \cup {i})\) produces the smallest string.

The problem becomes computing \(f(i, S)\) efficiently. If \(S\) contains all words, then \(f(i, S)\) returns \(words[i]\) for all possible values of \(i\). Note that it also covers the case where \(words\) has only one word. Otherwise, we have two or more words to cover, and we need to build the smallest string starting with \(words[i]\) that cover all words not in \(S\). For each word \(j \notin S\), find the longest prefix \(k\) of \(words[j]\) that is a suffix of \(words[i]\). We have that \(words[i][0..(k-1)]words[j]\) is the smallest string that covers both \(i\) and \(j\). Therefore, \(words[i][0..k(j)] \cdot f(j, S \cup {j})\) is a candidate solution for all \(j\) that is not in \(S\) and \(f(j, S \cup {j})\). To pick the solution for \(f(i, S)\), we can iterate over all candidates \(j\) and pick the one that produces the smallest string. The only problem left is to efficiently compute the longest suffix of two strings. This can be done by building a table \(suf\) where \(suf[i][j]\) is the index on \(words[i]\) of the longest suffix that is a prefix of \(words[j]\). There are \(n \times 2^n\) possible inputs for \(f\) and each one of them will run in \(O(n)\). So, the space complexity is \(O(n \times 2^n)\) and time complexity is \(O(n^2 \times 2^n)\).

from typing import List
from functools import cache


class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:
        N = len(words)
        ALL = (1 << N) - 1

        @cache
        def k(a, b):
            for i in range(len(words[a]) + 1):
                if words[b].startswith(words[a][i:]):
                    return i

        @cache
        def dfs(last, used):
            if used == ALL:
                return words[last]
            ans = None
            for i in range(N):
                if (1 << i) & used == 0:
                    cur = words[last][: k(last, i)] + dfs(i, used | (1 << i))
                    if ans is None or len(ans) > len(cur):
                        ans = cur
            return ans

        return min([dfs(i, (1 << i)) for i in range(N)], key=len)


assert (
    Solution().shortestSuperstring(["alex", "loves", "leetcode"]) == "alexlovesleetcode"
)
assert (
    Solution().shortestSuperstring(["catg", "ctaagt", "gcta", "ttca", "atgcatc"])
    == "gctaagttcatgcatc"
)