0943. Find the Shortest Superstring

题目信息

题号:

0943

难度:

Hard

主题:

字符串、重叠拼接、最短超串

原题:

LeetCode 0943

重点:

返回字符串必须把每个输入单词作为连续子串包含;目标是总长度最短,最短答案不唯一时可返回任意一个

题目重述

给定互不相同的字符串数组 words,并保证任意一个单词都不是另一个单词的子串。需要构造一个字符串,使 words 中的每个单词都在其中至少连续出现一次。

请返回长度最短的这种超字符串。拼接不同单词时可以利用一个单词后缀与另一个单词前缀的重叠部分。若存在多个长度同样最短的答案,可以返回任意一个。

1 <= words.length <= 12,1 <= words[i].length <= 20,单词只包含小写英文字母。

自建示例

三个单词首尾循环重叠:

输入:words = ["ab","bc","ca"]
输出:"abca"
解释:"abca" 同时包含 "ab"、"bc" 和 "ca",长度为 4;长度为 3 的字符串无法同时包含三个不同的两字符单词。其他同长度答案也可以返回。

数组只有一个单词:

输入:words = ["orbit"]
输出:"orbit"
解释:唯一单词本身已经是包含全部输入单词的最短超字符串,无法再删除任何字符。