Oleksii Trekhleb | Javascript algorithms (Shortest common supersequence)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 1 phút đọc.
The shortest common supersequence (SCS) of two sequences X and Y is the shortest sequence which has X and Y as subsequences.
In other words assume we’re given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.
This is a problem closely related to the longest common subsequence problem.
Example
Input: str1 = _geek,_ str2 = _eke_
Output: _geeke_
Input: str1 = _AGGTAB,_ str2 = _GXTXAYB_
Output: _AGXGTXAYB_
Share:
