find-the-shortest-superstring

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

You may assume that no string in <code>words</code> is a substring of another string in <code>words</code>.

&nbsp;
Example 1:

<pre>
Input: words = [&quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot;]
Output: &quot;alexlovesleetcode&quot;
Explanation: All permutations of &quot;alex&quot;,&quot;loves&quot;,&quot;leetcode&quot; would also be accepted.
</pre>

Example 2:

<pre>
Input: words = [&quot;catg&quot;,&quot;ctaagt&quot;,&quot;gcta&quot;,&quot;ttca&quot;,&quot;atgcatc&quot;]
Output: &quot;gctaagttcatgcatc&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 12</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 20</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
	<li>All the strings of <code>words</code> are unique.</li>
</ul>

shortestSuperstring

Find the Shortest Superstring

Maximum Rows Covered by Columns

maximum-rows-covered-by-columns

被列覆盖的最多行数

Find the Minimum Cost Array Permutation

find-the-minimum-cost-array-permutation

找出分数最低的排列

Find the Shortest Superstring II

find-the-shortest-superstring-ii

最短超级串 II

Bit Manipulation

Array

String

Dynamic Programming

Bitmask

给定一个字符串数组 <code>words</code>，找到以 <code>words</code> 中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件，返回其中 任意一个 即可。

我们可以假设 <code>words</code> 中没有字符串是 <code>words</code> 中另一个字符串的子字符串。

 

示例 1：

<pre>
输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。</pre>

示例 2：

<pre>
输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"</pre>

 

提示：

<ul>
	<li><code>1 <= words.length <= 12</code></li>
	<li><code>1 <= words[i].length <= 20</code></li>
	<li><code>words[i]</code> 由小写英文字母组成</li>
	<li><code>words</code> 中的所有字符串 互不相同</li>
</ul>