1092. Shortest Common Supersequence

题目信息

题号:

1092

难度:

Hard

主题:

两个字符串、公共超序列、最短构造

原题:

LeetCode 1092

重点:

返回的字符串必须同时包含 str1 和 str2 作为子序列,并在所有合法字符串中长度最短;最短答案不唯一时可返回任意一个

题目重述

给定两个小写字符串 str1 和 str2。若删除字符串 s 中若干字符且保持剩余字符相对顺序后可以得到某个字符串,则该字符串是 s 的子序列。

请构造一个最短字符串,使 str1 和 str2 都是它的子序列,并返回任意一个最短结果。结果可以在必要位置插入字符,但不能改变两个输入字符串各自的字符顺序。

1 <= str1.length, str2.length <= 1000,两个字符串只包含小写英文字母。

自建示例

共享字符只需在结果中保留一次:

输入:str1 = "abc", str2 = "bda"
输出:"abdac"
解释:abc 可由下标 0、1、4 得到,bda 可由下标 1、2、3 得到。两个输入的最长公共子序列长度为 1,因此任何公共超序列至少长 5,当前结果长度正好为 5。

两个输入完全相同:

输入:str1 = "cat", str2 = "cat"
输出:"cat"
解释:同一个字符串已经同时包含两个输入作为子序列,再增加字符只会使结果更长。