146. Shortest Common Supersequence via Array DP

Given two strings s1 and s2, return the length of their shortest common supersequence — the shortest string that has both s1 and s2 as subsequences. Input: '"s1", "s2"'.

Input: '"s1", "s2"'.

Output: Integer — length of SCS.

Examples

Input: "abac", "cab"
Output: 5
Explanation: SCS 'cabac' has length 5.

Input: "abc", "abc"
Output: 3
Explanation: Identical strings.

Input: "", "abc"
Output: 3
Explanation: SCS is 'abc'.

Constraints

• 0<=s1.length,s2.length<=1000

Asked by