Skip to content

Latest commit

 

History

History
40 lines (23 loc) · 1.11 KB

1092-shortest-common-supersequence.adoc

File metadata and controls

40 lines (23 loc) · 1.11 KB

1092. Shortest Common Supersequence

{leetcode}/problems/shortest-common-supersequence/[LeetCode - Shortest Common Supersequence ^]

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)

Example 1:

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

Note:

  1. 1 ⇐ str1.length, str2.length ⇐ 1000

  2. str1 and str2 consist of lowercase English letters.

link:{sourcedir}/_1092_ShortestCommonSupersequence.java[role=include]