1092. Shortest Common Supersequence¶
题目信息¶
- 题号:
1092
- 难度:
Hard
- 主题:
两个字符串、公共超序列、最短构造
- 原题:
- 重点:
返回的字符串必须同时包含
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"
解释:同一个字符串已经同时包含两个输入作为子序列,再增加字符只会使结果更长。