You are given two strings, str1 and str2. Your task is to find the shortest common supersequence (SCS). The shortest possible string that contains both str1 and str2 as subsequences.
If multiple strings satisfy this condition, you may return any one of them.
Note: A string
s is considered a subsequence of another stringt ifs can be obtained by deleting zero or more characters fromt without changing the order of the remaining characters.
Constraints:
str1.length, str2.length
str1 and str2 consist of lowercase English letters.
The problem asks for the shortest string that contains both str1 and str2 as subsequences. This problem naturally lends itself to dynamic programming, as the shortest common supersequence (SCS) is closely related to the longest common subsequence (LCS). The key insight is that any characters shared between the two strings only need to appear once in the final result, and the LCS tells us exactly which characters those are. By combining the shared characters from the LCS with the remaining non-common characters, we can build the shortest sequence that still preserves the relative order of both input strings.
The essence of the solution is to first calculate the lengths of the LCS for all prefixes of the two strings and store them in a DP table. This table then serves as a guide for constructing the final supersequence. We work backward from the end of both strings:
Whenever the characters match, that character is part of the LCS and is included in the result once.
When they differ, both characters eventually need to appear in the SCS, but we choose which one to place next by consulting the DP table, moving in the direction that corresponds to a longer LCS.
This ensures that shared characters are preserved in order and unique characters are interleaved correctly, producing the shortest valid supersequence.
The algorithm can be broken down into the following steps:
We start by creating a 2D DP table lcs of size
You are given two strings, str1 and str2. Your task is to find the shortest common supersequence (SCS). The shortest possible string that contains both str1 and str2 as subsequences.
If multiple strings satisfy this condition, you may return any one of them.
Note: A string
s is considered a subsequence of another stringt ifs can be obtained by deleting zero or more characters fromt without changing the order of the remaining characters.
Constraints:
str1.length, str2.length
str1 and str2 consist of lowercase English letters.
The problem asks for the shortest string that contains both str1 and str2 as subsequences. This problem naturally lends itself to dynamic programming, as the shortest common supersequence (SCS) is closely related to the longest common subsequence (LCS). The key insight is that any characters shared between the two strings only need to appear once in the final result, and the LCS tells us exactly which characters those are. By combining the shared characters from the LCS with the remaining non-common characters, we can build the shortest sequence that still preserves the relative order of both input strings.
The essence of the solution is to first calculate the lengths of the LCS for all prefixes of the two strings and store them in a DP table. This table then serves as a guide for constructing the final supersequence. We work backward from the end of both strings:
Whenever the characters match, that character is part of the LCS and is included in the result once.
When they differ, both characters eventually need to appear in the SCS, but we choose which one to place next by consulting the DP table, moving in the direction that corresponds to a longer LCS.
This ensures that shared characters are preserved in order and unique characters are interleaved correctly, producing the shortest valid supersequence.
The algorithm can be broken down into the following steps:
We start by creating a 2D DP table lcs of size