#943

Find the Shortest Superstring

hard · failed · 45.1% accepted · 1,516 likes · top 28%

array · string · dynamic programming · bit manipulation · bitmask

⊣ practice⊣ open on leetcode ↗

Description

Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.

You may assume that no string in words is a substring of another string in words.

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Solution