1092. 最短公共超序列【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 解法 1

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

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

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

---

提示：

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 都由小写英文字母组成。

2. 🎯 s.1 - 解法 1

js

// todo

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$