shortest-common-supersequence

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 two strings <code>str1</code> and <code>str2</code>, return the shortest string that has both <code>str1</code> and <code>str2</code> as subsequences. If there are multiple valid strings, return any of them.

A string <code>s</code> is a subsequence of string <code>t</code> if deleting some number of characters from <code>t</code> (possibly <code>0</code>) results in the string <code>s</code>.

&nbsp;
Example 1:

<pre>
Input: str1 = &quot;abac&quot;, str2 = &quot;cab&quot;
Output: &quot;cabac&quot;
Explanation: 
str1 = &quot;abac&quot; is a subsequence of &quot;cabac&quot; because we can delete the first &quot;c&quot;.
str2 = &quot;cab&quot; is a subsequence of &quot;cabac&quot; because we can delete the last &quot;ac&quot;.
The answer provided is the shortest such string that satisfies these properties.
</pre>

Example 2:

<pre>
Input: str1 = &quot;aaaaaaaa&quot;, str2 = &quot;aaaaaaaa&quot;
Output: &quot;aaaaaaaa&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>
	<li><code>str1</code> and <code>str2</code> consist of lowercase English letters.</li>
</ul>

shortestCommonSupersequence

Shortest Common Supersequence 

Longest Common Subsequence

longest-common-subsequence

最长公共子序列

Shortest String That Contains Three Strings

shortest-string-that-contains-three-strings

包含三个字符串的最短字符串

String

Dynamic Programming

给你两个字符串&nbsp;<code>str1</code> 和&nbsp;<code>str2</code>，返回同时以&nbsp;<code>str1</code>&nbsp;和&nbsp;<code>str2</code>&nbsp;作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 <code>t</code> 中删除一些字符（也可能不删除），可以得到字符串 <code>s</code> ，那么 <code>s</code> 就是 t 的一个子序列。

&nbsp;

示例 1：

<pre>
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。
</pre>

示例 2：

<pre>
输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>
	<li><code>str1</code> 和&nbsp;<code>str2</code>&nbsp;都由小写英文字母组成。</li>
</ul>