Shortest Common Supersequence Length
Medium · dynamic programming
A word w is a subsequence of a longer word if you can get w by deleting some letters (possibly none) from the longer word without changing the order of the rest. For example, ace is a subsequence of abcde, but eca is not.
You are given two words, s and t. Find the shortest word that has both s and t as subsequences, and return its length. You do not need to build the word itself.
Either word may be empty. If one word is empty, the answer is the length of the other.
Examples
Example 1
Input: s = "abac", t = "cab"
Output: 5
The word "cabac" contains "abac" (its last four letters) and "cab" (its first three). No word of length 4 or less contains both.
Example 2
Input: s = "ab", t = "ab"
Output: 2
The word itself already contains both.
Example 3
Input: s = "aaa", t = "bbb"
Output: 6
The words share no letters, so nothing can be reused and the answer is 3 + 3.
Constraints
- 0 <= len(s), len(t) <= 1000
- Both words contain only lowercase English letters.