943. Find the Shortest Superstring

[zeikar]

Problem link

https://leetcode.com/problems/find-the-shortest-superstring/

Problem Summary

모든 단어를 substring으로 갖는 가장 짧은 문자열을 구하는 문제.

Solution

처음에는 어려운데 비트마스크 DP를 쓰면 된다.
단어들을 뒤로 이어붙인다고 생각하고, 붙인 단어는 visited 처리를 비트마스크로 할 수 있다.

이러면 꽤 풀만한 문제가 된다.

suffix 함수는 단어를 뒤로 붙일 때 앞 단어의 중복되는 부분을 제거한 suffix 만 추출하는 함수이다.
마지막 words에 빈 문자열을 더하는건 코드를 간결하게 하기 위함이다.

전체 흐름은 디스커션 참고함. (https://leetcode.com/problems/find-the-shortest-superstring/discuss/1225543/Python-dp-on-subsets-solution-3-solutions-%2B-oneliner-explained)

Source Code

from functools import lru_cache
from typing import List


class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:

        n = len(words)

        # abc, bcd => d
        @lru_cache(None)
        def suffix(w1, w2):
            for i in range(len(words[w1]), -1, -1):
                if words[w1][-i:] == words[w2][:i]:
                    return words[w2][i:]
            return words[w2]

        @lru_cache(None)
        def solve(visited, last):
            # all visited
            if visited == (1 << n) - 1:
                return ""

            ret = ""

            for i in range(n):
                if visited & (1 << i) == 0:
                    res = suffix(last, i) + solve(visited | (1 << i), i)
                    if len(ret) == 0 or len(res) < len(ret):
                        ret = res

            return ret

        words += [""]
        return solve(0, -1)