You are given two strings a and b consisting of lowercase English letters.
A subsequence of a string is obtained by deleting zero or more characters without changing the order of the remaining ones. A common supersequence of a and b is a string that has both a and b as subsequences.
Return the length of the shortest common supersequence of a and b. Either string may be empty, in which case the shortest common supersequence is just the other string.
Examples
Example 1
Input: a = "abac", b = "cab"
Output: 5
Explanation: "cabac" has both "abac" and "cab" as subsequences, and no shorter string does.
Example 2
Input: a = "abc", b = "abc"
Output: 3
Explanation: "abc" already has itself as a subsequence, so it is its own shortest common supersequence.
Example 3
Input: a = "abc", b = "def"
Output: 6
Explanation: The strings share no characters, so the shortest common supersequence is just one after the other.
Constraints
0≤a.length, b.length≤1000
a and b consist of lowercase English letters only
Loading editor...
Log in to run your code. Your draft is saved in this browser.Log inSign up