778. Edit Distance (Recursive + Memoization)

Given two strings s1 and s2, return the MINIMUM number of operations required to convert s1 into s2. The allowed operations on either string are:
1. Insert a character.
2. Delete a character.
3. Replace a character.
Implement the solution with recursion + memoization.

Input is two quoted strings separated by a comma.

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

Output: Return an integer — the edit (Levenshtein) distance.

Examples

Input: "horse", "ros"
Output: 3
Explanation: horse -> rorse (replace) -> rose (delete) -> ros (delete).

Input: "intention", "execution"
Output: 5
Explanation: Five operations needed.

Input: "abc", "abc"
Output: 0
Explanation: Already identical.

Constraints

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

Asked by