1092. Shortest Common Supersequence =================================== 题目信息 -------- :题号: 1092 :难度: Hard :主题: 两个字符串、公共超序列、最短构造 :原题: `LeetCode 1092 `_ :重点: 返回的字符串必须同时包含 ``str1`` 和 ``str2`` 作为子序列,并在所有合法字符串中长度最短;最短答案不唯一时可返回任意一个 题目重述 -------- 给定两个小写字符串 ``str1`` 和 ``str2``。若删除字符串 ``s`` 中若干字符且保持剩余字符相对顺序后可以得到某个字符串,则该字符串是 ``s`` 的子序列。 请构造一个最短字符串,使 ``str1`` 和 ``str2`` 都是它的子序列,并返回任意一个最短结果。结果可以在必要位置插入字符,但不能改变两个输入字符串各自的字符顺序。 ``1 <= str1.length, str2.length <= 1000``,两个字符串只包含小写英文字母。 自建示例 -------- 共享字符只需在结果中保留一次: .. code-block:: text 输入:str1 = "abc", str2 = "bda" 输出:"abdac" 解释:abc 可由下标 0、1、4 得到,bda 可由下标 1、2、3 得到。两个输入的最长公共子序列长度为 1,因此任何公共超序列至少长 5,当前结果长度正好为 5。 两个输入完全相同: .. code-block:: text 输入:str1 = "cat", str2 = "cat" 输出:"cat" 解释:同一个字符串已经同时包含两个输入作为子序列,再增加字符只会使结果更长。