#1092

Shortest Common Supersequence

expert · 1135 · lc hard +32 · verified · 61.8% accepted · 5,912 likes · top 62%

⚑ Linear 1D DP ⚑ String Matching DP (LCS / Edit Distance)

Description

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

A string s is a subsequence of t if s can be obtained from t by deleting some characters without changing order.

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.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"

Output: "aaaaaaaa"

Code

1

2

3

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str: