776. Longest Common Subsequence (Recursive + Memoization)

Given two strings s1 and s2, return the LENGTH of their longest common subsequence (LCS). A subsequence is a sequence that can be derived by deleting some or no characters without changing the relative order. If there is no common subsequence, return 0. Implement with recursion + memoization.

Input is two quoted strings separated by a comma, e.g. "abc", "def".

Input: Two strings in quotes separated by ', '.

Output: Return an integer — the LCS length.

Examples

Input: "abcde", "ace"
Output: 3
Explanation: LCS is 'ace' with length 3.

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

Input: "abc", "def"
Output: 0
Explanation: No common subsequence.

Constraints

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

Asked by