#943
Find the Shortest Superstring
candidate master · 1565 · lc hard +32 · failed · 45.1% accepted · 1,516 likes · top 28%
Description
You need a single string that contains each element of words as a contiguous substring (no word in words is already a substring of another). Maximize overlaps between words to minimize total length. Return any valid shortest superstring.
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"
Code
1
2
3